10/02/21 08:46:43
[1] 授業単元：
UNIX C Programming
[2] 問題文(含コード&リンク)：
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
[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:デフォルトの名無しさん
10/02/21 15:06:11
>>713です。みなさんサンクスです。動かして確認してみます。
748:デフォルトの名無しさん
10/02/21 23:08:02
>>745
1000個のほうはあってたよ。
10000個のほうは、おれの作った糞ツールでは、検証不能ｗ
よかったらソースうｐしてくれないか？
ちなみに>747とは別人です。
749:738
10/02/22 00:03:29
>>713
>>748
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
6割近く何も指してないのが気に入らない
750:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/02/22 10:46:32
floor(n^(1/3))でいけそうなものだけどだめなのかね
752:デフォルトの名無しさん
10/02/22 10:48:17
ceilだねごめん。
753:デフォルトの名無しさん
10/02/22 12:59:14
リンク3、リンク4で賄える最大ページ数を求める方が良いと思う。
それが決まればその表引きで求まる。
754:デフォルトの名無しさん
10/02/22 15:17:41
どの2点とっても、3つ以内の矢印でつながってるってことだろ。
総当たりやると矢印生成でかなり時間かかるな。
それを全ての2点でつながるかチェック。このチェックは時間かからないが、塵も積もれば山となる。
755:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/02/22 15:39:56
このスレでちょくちょく出る宿題のテーマの道具
使えば最適解とは違うかも知れないがそれに肉薄
するのは簡単に出せるだろ？
但しヒューリスティックス系はC/C++では
書かないほうがいい。個人でやるのは止められないが
ネット公開するのはやめたほうがいい。今時。
757:デフォルトの名無しさん
10/02/22 15:42:47
1000は18で出来るらしいが17以下の解見つけた人
758:デフォルトの名無しさん
10/02/22 16:25:32
>>746
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
汚くなってしまいましたが、どうぞ。
759:548
10/02/22 16:53:39
>>579
>>580
無事提出できました。
ありがとうございました。最初は
どちらのほうを参考にさせてもらえ
ばよいのか悩みましたが、結局
友達と相談しながらやったらみなさんと
同じ結果が出るようになったので
そちらをだしました。
760:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/02/22 19:36:20
金太郎飴方式 yowa
762:デフォルトの名無しさん
10/02/22 19:38:26
>>760
どこが金太郎飴かわからんけど、その調子でもう少し書いてみようか
763:デフォルトの名無しさん
10/02/22 19:46:01
金太郎飴方式 towa?
764:デフォルトの名無しさん
10/02/22 19:49:27
ろだで10539で質問した者ですが、また質問です。入門書などによくある＊印でピラミッドを造るプログラムを作ったのですが、10行目と11行目の部分は削除しても同じように動作しました。
なぜでしょうか？
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
765:デフォルトの名無しさん
10/02/22 19:54:01
>>764
バイナリが更新されていないからじゃないかな
766:デフォルトの名無しさん
10/02/22 19:57:07
>>765
どういう意味なのでしょうか？
767:デフォルトの名無しさん
10/02/22 19:57:42
>>762
問題によっては最適解近辺は金太郎飴の断面みたい
な状況であることを原理とした探索法のことではな
いかと想像
768:デフォルトの名無しさん
10/02/22 20:03:46
>>766
修正前の実行ファイルを動かしたまま ソース修正
→ コンパイル
→ リンク （で、実行ファイルが上書きできなくて エラー）
→ 再実行 →あれ？ 古いままの挙動じゃん
→ 実行ファイルのタイムスタンプ確認 ｱﾁｬｰ
769:デフォルトの名無しさん
10/02/22 20:06:04
>>768
試してみましたが、それはないと思います。実際自分が作ったものは10.11行があっても動きますが、実際本に書いてあるのは
それの10,11行目がないものが書いてありました。
770:デフォルトの名無しさん
10/02/22 20:08:33
>>768
申し訳ありません。もう一度試してみたらうまくいきました。どうやらその行をctrl+xで切り取ったあと再び貼り付けてしまったようでした。
本当に申し訳ありませんでした。
771:デフォルトの名無しさん
10/02/22 20:09:20
俺試してみたけど削除したらピラミッドなんて出てこんよ
772:デフォルトの名無しさん
10/02/22 20:12:09
>>764
こちらで試したところでは、１０行目、１１行目を省くとピラミッドにはなりませんでした。
段数を入力してください。(0から40まで)
5
*
*
*
*
*
773:デフォルトの名無しさん
10/02/22 20:17:30
>>770
>うまくいきましたというのは768さんのいう通りということです。
すいません。
774:デフォルトの名無しさん
10/02/22 20:22:32
つまり？
775:デフォルトの名無しさん
10/02/22 20:24:16
>>774
?
776:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/02/22 20:37:05
>>750のように一つずつずらしていけば、3クリック以内で到達できるようにできるってことか。
779:デフォルトの名無しさん
10/02/22 20:44:05
1000なら10個でいいってこと?
1000から999へいけるか。
1000 -> 1(2-11) -> 11(102-110) -> 110で最大到達地点は110では。
780:デフォルトの名無しさん
10/02/22 20:46:45
間違えた。一手目が1だけではない。再考する。
781:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/02/22 20:59:44
>>776
9通りがよくわからなかったが今わかった。1は自分自身に向かわせてるからね。
2から初めて他所で自分自身に向かわなければこっちの方が効率良いはず。
783:デフォルトの名無しさん
10/02/22 21:02:36
一番重要なことは、金太郎飴方式だと、
リンク先のユニーク性を簡単に確保できることだね。
N^3 + N^2 + N + 1 >= N
この付近が最適解だってのはわかってたけど、
ユニーク性の確保が悩みの種だったし。
1クリック目のとび先と、2クリック目の飛び先がかぶってたら
大きなロスになるし。
784:デフォルトの名無しさん
10/02/22 21:52:22
max(links(n)) * Σlinks(n)
これで評価してみれば？
785:デフォルトの名無しさん
10/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