- 1 名前：デフォルトの名無しさん [2010/01/18(月) 23:25:55 BE:265079647-S★(508111)]
- あなたが解けないC言語/C++言語の宿題を片付けもらうスレッドです。気に入らない質問やその他の発言はスルーの方向で。
【質問者へ】
回答者の便宜のため、質問の際は以下を行うことを推奨します。
・質問は【質問テンプレ】を利用してください。
・問題文は、出題されたまま全文を書いてください。
・問題文やコードをリンクするときは、一言内容にについて説明をつけましょう。
・計算問題は数式をあげ、どのような計算をするのか詳しく説明してください。
・エラーは、その詳細と発生した行を書きましょう。エラーメッセージはコピペしてください。
・後から問題に付け足しするのはコラー！！です。付け足しは作業を無駄にしがちです。
・なりすましを防ぐため、トリップを使ってください。名前欄に、「#」に続けて任意の文字列を入力して投稿すると、その文字列を知らない他人に騙られることを防ぐことができます。
【質問テンプレ】
[1] 授業単元：
[2] 問題文(含コード&リンク)：
[3] 環境
[3.1] OS： (Windows/Linux/等々)
[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)
[3.3] 言語： (C/C++/どちらでも可 のいずれか)
[4] 期限： ([yyyy年mm月dd日hh:mmまで] または [無期限] のいずれか)
[5] その他の制限： (どこまで習っているか、標準ライブラリは使ってはいけない等々)
【アップローダー==ラウンジ】(質問が長い時はココ使うと便利 回答者もコードが長ければここに)
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/joyful.htm
【C 関数検索 man on WWW】 www.linux.or.jp/JM/index.html
【過去ログ検索】 chomework.sakura.ne.jp/
【wiki】 www23.atwiki.jp/homework/
前スレ
C/C++の宿題片付けます 133代目
pc12.2ch.net/test/read.cgi/tech/1260532772/
- 736 名前： ◆/91kCCQXBo mailto:sage [2010/02/20(土) 11:05:35 ]
- なんか、今見たら違ってる。
- 737 名前： ◆/91kCCQXBo mailto:sage [2010/02/20(土) 13:18:05 ]
- もっと減らせそう
#include<stdio.h>
int main(void){
int n,m,i,j;
float ans;
/* 解答 */
printf("ページ数：");
scanf("%d%*c", &n); m=n;
ans = (n+1)/3.0;
if((n=ans) != n) n++;
printf("\n%d[page] %d[link/page]", m, n);
/* 結果 */
for(i=1;i<=m;i++){
printf("\n%d:",i);
for(j=0;j<n;j++){
printf("%d ", (i + j*3)%m+1 );
}
}
puts(""); return 0;
}
- 738 名前：デフォルトの名無しさん mailto:sage [2010/02/20(土) 14:17:55 ]
- >>737
>>722 のアルゴリズムの場合
ページ数 20 のときリンクの最大数は 4
これより減ることはあっても増えるのは無しだろう
1 : 2 3 4 5
2 : 1 6 7 8
3 : 1 2 9 10
4 : 1 2 11 12
5 : 1 2 13 14
6 : 1 2 15 16
7 : 1 2 17 18
8 : 1 2 19 20
9 : 1 2
10 : 1 2
11 : 1 2
12 : 1 2
13 : 1 2
14 : 1 2
15 : 1 2
16 : 1 2
17 : 1 2
18 : 1 2
19 : 1 2
20 : 1 2
- 739 名前：738 mailto:sage [2010/02/20(土) 14:50:48 ]
- >>722 のアルゴリズムじゃねーｗ
- 740 名前：デフォルトの名無しさん mailto:sage [2010/02/20(土) 21:27:37 ]
- 実際にリンク組んで確かめるプログラムはないんですか。
- 741 名前：デフォルトの名無しさん mailto:sage [2010/02/20(土) 23:30:28 ]
- ていうか、あってるかどうか確認するプログラムって、オーダはどうなる？
ページ数をN、最大クリック数をCとしたら、NCでできるのか？
- 742 名前：デフォルトの名無しさん mailto:sage [2010/02/21(日) 00:10:35 ]
- U個のユニットに分け、ユニットをそれぞれG個のグループに分ける。
各々のグループにはn枚目のページがあるとする。
また、n >= Uという条件をつける。
このとき、総ページ数N = U*G*n
まず、グループ内のn枚のページで、相互リンクを貼る。
相互リンクの数は (n-1)個
次に、グループ内のm枚目のページにm番目のユニットの各々のグループ内のページ(どれでもいい)各1枚へのリンクを貼る。
グループ外リンクの数は、G個
こうすると、(ユニット, グループ, ページ) = (u1, g1, p1)から(u2, g2, p2)へ行くのに、最大でも
(u1, g1, p1) -> (u1, g1, u2) -> (u2, g2, ??) -> (u2, g2, p2)の3クリックで行ける。
また、このとき合計リンク数はG + (n-1)個
G + (n-1)が最小となり、N = U*G*n, n >= Uを満たす数字を考えると
・まず、Uを増やして数を稼ぎたいので、U=n
・よって、N=G*n^2を満たし、G+(n-1)が最小となるn, Gを求める
・計算の結果、それはn^3=2N, G=n/2のとき
- 743 名前：デフォルトの名無しさん mailto:sage [2010/02/21(日) 00:19:18 ]
- 例えば、64ページあるとき、
Unit 0{
Group 0{ Page 0 = [(0,0,1), (0,0,2),(0,0,3),(0,1,0)], Page 1 = [(0,0,1), (0,0,2),(0,0,3),(1,0,0),(1,1,0)], ...}
Group 1{ Page 0 = [(0,1,1), (0,1,2),(0,1,3),(0,0,0)], Page 1 = [(0,1,1), (0,1,2),(0,1,3),(1,0,0),(1,1,0)], ...}
}
Unit 1{
Group 0{ Page 0 = [(1,0,1), (1,0,2),(1,0,3),(0,0,0),(0,1,0)], Page 1 = [(1,0,1), (1,0,2),(1,0,3),(1,1,0)], ...}
Group 1{ Page 0 = [(1,1,1), (1,1,2),(1,1,3),(0,0,0),(0,1,0)], Page 1 = [(1,1,1), (1,1,2),(1,1,3),(1,0,0)], ...}
}
...
になって、グループ数=2, ユニット数=ページ数=4で、最大リンク数は5
- 744 名前：デフォルトの名無しさん mailto:sage [2010/02/21(日) 00:57:26 ]
- ヒューリスティックアプローチを探したいものだが
C/C++言語ではやめたほうがいいかも
VM上で実行できる処理系でないと
カーネルコードが書ける処理系ではお勧め出来ない
- 745 名前：738 mailto:sage [2010/02/21(日) 02:02:28 ]
- >>738 のアルゴリズムで解いた結果は
総ページ数 1000 のとき、最大リンク数 18
総ページ数 10000 のとき、最大リンク数 40
合ってるかどうか未確認
詳細内容 50kB
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10538.lzh
- 746 名前：デフォルトの名無しさん [2010/02/21(日) 08:46:43 ]
- [1] 授業単元：
UNIX C Programming
[2] 問題文(含コード&リンク)：
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10541.txt
[3] 環境
[3.1] OS： (Windows/Linux/等々)
Mac OSX 10.5.8
[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)
gcc 4.0.1
[3.3] 言語： どちらでも可
[4] 期限： 2010年2月24日夜７時まで
[5] その他の制限：
可能であれば強引な方法でも構いません。
上記リンクはCで書いてありますが、C++でも構いません。
何卒よろしくお願いします。
- 747 名前：デフォルトの名無しさん mailto:sage [2010/02/21(日) 15:06:11 ]
- >>713です。みなさんサンクスです。動かして確認してみます。
- 748 名前：デフォルトの名無しさん mailto:sage [2010/02/21(日) 23:08:02 ]
- >>745
1000個のほうはあってたよ。
10000個のほうは、おれの作った糞ツールでは、検証不能ｗ
よかったらソースうｐしてくれないか？
ちなみに>747とは別人です。
- 749 名前：738 mailto:sage [2010/02/22(月) 00:03:29 ]
- >>713
>>748
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10543.c
6割近く何も指してないのが気に入らない
- 750 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 09:03:49 ]
- >749
ありがと。
ここにあがってる回答はどれも不正解だった。
自分も正解はわからないけど、手計算で次の最適解を発見した。
ページ数 8 の答えは 2
ページ数 12 の答えは 3
ページ数 8 の最適解の例
1: 2 3
2: 4 5
3: 6 7
4: 8 1
5: 2 3
6: 4 5
7: 6 7
8: 8 1
- 751 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 10:46:32 ]
- floor(n^(1/3))でいけそうなものだけどだめなのかね
- 752 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 10:48:17 ]
- ceilだねごめん。
- 753 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 12:59:14 ]
- リンク3、リンク4で賄える最大ページ数を求める方が良いと思う。
それが決まればその表引きで求まる。
- 754 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 15:17:41 ]
- どの2点とっても、3つ以内の矢印でつながってるってことだろ。
総当たりやると矢印生成でかなり時間かかるな。
それを全ての2点でつながるかチェック。このチェックは時間かからないが、塵も積もれば山となる。
- 755 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 15:24:23 ]
- 同じ場所へ複数リンクが付くと無駄なので、最大リンク3なら
初めの方はリンクがかぶらないように配置していいはずだな。
リンク3なら、総数が3*3*3=27より上には出来ないから、この範囲で増減しながらしらみつぶしでやるか。
1: 2 3 4
2: 5 6 7
3: 8 9 10
4: 11 12 13
- 756 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 15:39:56 ]
- このスレでちょくちょく出る宿題のテーマの道具
使えば最適解とは違うかも知れないがそれに肉薄
するのは簡単に出せるだろ？
但しヒューリスティックス系はC/C++では
書かないほうがいい。個人でやるのは止められないが
ネット公開するのはやめたほうがいい。今時。
- 757 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 15:42:47 ]
- 1000は18で出来るらしいが17以下の解見つけた人
- 758 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 16:25:32 ]
- >>746
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10545.txt
汚くなってしまいましたが、どうぞ。
- 759 名前：548 mailto:sage [2010/02/22(月) 16:53:39 ]
- >>579
>>580
無事提出できました。
ありがとうございました。最初は
どちらのほうを参考にさせてもらえ
ばよいのか悩みましたが、結局
友達と相談しながらやったらみなさんと
同じ結果が出るようになったので
そちらをだしました。
- 760 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:13:50 ]
- >>757
1: 1 2 3 4 5 6 7 8 9 10
2: 11 12 13 14 15 16 17 18 19 20
以下略
金太郎飴方式恐るべし
- 761 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:36:20 ]
- 金太郎飴方式 yowa
- 762 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:38:26 ]
- >>760
どこが金太郎飴かわからんけど、その調子でもう少し書いてみようか
- 763 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:46:01 ]
- 金太郎飴方式 towa?
- 764 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:49:27 ]
- ろだで10539で質問した者ですが、また質問です。入門書などによくある＊印でピラミッドを造るプログラムを作ったのですが、10行目と11行目の部分は削除しても同じように動作しました。
なぜでしょうか？
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10546.c
- 765 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:54:01 ]
- >>764
バイナリが更新されていないからじゃないかな
- 766 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:57:07 ]
- >>765
どういう意味なのでしょうか？
- 767 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 19:57:42 ]
- >>762
問題によっては最適解近辺は金太郎飴の断面みたい
な状況であることを原理とした探索法のことではな
いかと想像
- 768 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:03:46 ]
- >>766
修正前の実行ファイルを動かしたまま ソース修正
→ コンパイル
→ リンク （で、実行ファイルが上書きできなくて エラー）
→ 再実行 →あれ？ 古いままの挙動じゃん
→ 実行ファイルのタイムスタンプ確認 ｱﾁｬｰ
- 769 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:06:04 ]
- >>768
試してみましたが、それはないと思います。実際自分が作ったものは10.11行があっても動きますが、実際本に書いてあるのは
それの10,11行目がないものが書いてありました。
- 770 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:08:33 ]
- >>768
申し訳ありません。もう一度試してみたらうまくいきました。どうやらその行をctrl+xで切り取ったあと再び貼り付けてしまったようでした。
本当に申し訳ありませんでした。
- 771 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:09:20 ]
- 俺試してみたけど削除したらピラミッドなんて出てこんよ
- 772 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:12:09 ]
- >>764
こちらで試したところでは、１０行目、１１行目を省くとピラミッドにはなりませんでした。
段数を入力してください。(0から40まで)
5
*
*
*
*
*
- 773 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:17:30 ]
- >>770
>うまくいきましたというのは768さんのいう通りということです。
すいません。
- 774 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:22:32 ]
- つまり？
- 775 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:24:16 ]
- >>774
?
- 776 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:24:51 ]
- >763
どこを切り取ってみても、数字がおなじ規則で並んでいる。
>760 の 1 の例だと
1 クリック目 9 種類のページにアクセス可能
2 クリック目 9 * 10 種類のページにアクセス可能
3 クリック目 9 * 10 * 10 種類のページにアクセス可能
もともといたページを含めて、ちょうど千種類のページにアクセスできる。
これは、どこを切り取ってみても、同じように数字が並んでいるので、
1 以外の数字についてもあてはまる。
規則的にならんでいるので、検証するにしても、
1 だけ検証できれば全部ＯＫみたいな感じ。
1クリック目の選択肢が 9 種類しかなくて、n^3 の爆発力をかなり損しているけど
ぎりぎり届いてた。n^3 の爆発力が重要な問題だった。
- 777 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:25:41 ]
- 数学的なことはわからんけど、こんな法則をみつけた。
a = pow(N, 1/3) /* ページ数の３乗根をとる */
min = floor(a) /* 天井とそこをとる */
max = ceil(a)
min = pow(min, 3) /* ３乗して元に戻す */
max = pow(max, 3)
if(min < N && N <= max) { /* レンジに収まってれば */
printf("答えは %f だよ", ceil(a))
}
else {
printf("答えは %f だよ", floor(a))
}
- 778 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:37:05 ]
- >>750のように一つずつずらしていけば、3クリック以内で到達できるようにできるってことか。
- 779 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:44:05 ]
- 1000なら10個でいいってこと?
1000から999へいけるか。
1000 -> 1(2-11) -> 11(102-110) -> 110で最大到達地点は110では。
- 780 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:46:45 ]
- 間違えた。一手目が1だけではない。再考する。
- 781 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:56:59 ]
- 1から初めて全部いけそうだな。他の数字も純粋しているだけだから同様ってことか。
1 2-
2 12-
3 22-
・・・・
10 92-
11 102-
12 112-
・・・・
100 992-
・・・・
998 972-
999 982-
1000 992-
- 782 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 20:59:44 ]
- >>776
9通りがよくわからなかったが今わかった。1は自分自身に向かわせてるからね。
2から初めて他所で自分自身に向かわなければこっちの方が効率良いはず。
- 783 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 21:02:36 ]
- 一番重要なことは、金太郎飴方式だと、
リンク先のユニーク性を簡単に確保できることだね。
N^3 + N^2 + N + 1 >= N
この付近が最適解だってのはわかってたけど、
ユニーク性の確保が悩みの種だったし。
1クリック目のとび先と、2クリック目の飛び先がかぶってたら
大きなロスになるし。
- 784 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 21:52:22 ]
- max(links(n)) * Σlinks(n)
これで評価してみれば？
- 785 名前：デフォルトの名無しさん mailto:sage [2010/02/22(月) 22:16:13 ]
- N=8の時の金太郎飴状態なリンク例
1:4 7
2:1 7
3:1 6
4:7
5:1 6
6:1 8
7:5 8
8:2 3
|
 |
