10/02/15 12:33:42
>>654
プログラムを組む以前の問題として、どうゆう回答をすれば先生が満足するのか
そこがイマイチ不明だ・・・。
傾向が似ているかどうか、というだけなら、各教科の得点を偏差値に変換して、
5次元空間上にプロットした時に、任意の生徒Aとのユークリッド距離が
最も近い生徒を選べばいい気がする・・・。
仮にそれでいいとして、高速抽出するためのデータ構造を組め、ってなると
要は任意の生徒Aに最も近い得点の傾向の生徒Bを予め計算しておいて
AとBを対で持たせておけばいいとか、そうゆうことかな？
657:デフォルトの名無しさん
10/02/15 12:44:28
モデル化してそれに最適なデータ構造考えろと言ってるんだろ。
モデル化の部分はこれまで授業で触れられていると思う。
658:デフォルトの名無しさん
10/02/15 13:54:43
>>654
皆全員０点だった場合は誰を選べばいい？
659:デフォルトの名無しさん
10/02/15 14:14:59
誰でもいいんじゃね？ みんな一緒だし。
660:デフォルトの名無しさん
10/02/15 14:16:28
656 のやり方で、データを読み込むとき予めソートしておくというのはどう？
661:デフォルトの名無しさん
10/02/15 14:17:26
日本語おかしいな。
データを読み込むときソートした状態にスレばいいんじゃないか？
662:デフォルトの名無しさん
10/02/15 14:19:12
>>654
極端な例の場合
ある生徒の得点分布が(50,51,52,53,54)
の場合(52,52,52,52,52)よりも(95,96,97,98,99)
の人のほうを選出したほうがいいの？
663:デフォルトの名無しさん
10/02/15 15:04:57
(0,20,40,60,100)のほうが近いとｵﾓ
664:デフォルトの名無しさん
10/02/15 15:42:32
単に差を出したらダメって言ってるんだから、{52,52,52,52,52}だろうよ
665:デフォルトの名無しさん
10/02/15 17:17:46
>>654
「傾向が近い」というのは、例えば
A (70,63,77)
B (70,70,70)
C (90,81,99)
だと、A≒B じゃなくて A≒C、という解釈
・・・でいいのか？
666:デフォルトの名無しさん
10/02/15 17:32:36
1) 合計の偏差値を取り、Aに近い10%を抽出候補を絞る
2) 五科目点数の総当たりの大小比較を行い、Aと共通なら1異なったら0として
その合計が最大のBを選出。
3) Bが複数出たらさてどうするか。
667:デフォルトの名無しさん
10/02/15 18:21:10
取り敢えずまだまだC言語で純正に一気に解決終了！
って出来る問題じゃなさそうだな
数学の複素多様体の知識とかデータベースの知識も要りそう
な問題で他のシステム（殆どが固有の言語を持つ）との
連携も要るような..
668:デフォルトの名無しさん
10/02/15 18:23:34
[4] 期限： 無期限
てのも何かコエーよｗ
669:デフォルトの名無しさん
10/02/15 18:29:58
foreach(生徒 in 生徒たち) {
if(指定生徒 == 生徒) continue;
match_average = 0;
for(科目番号 = 0; 科目番号 < 5; 科目番号++) {
diff = 生徒の得点[科目番号] - 指定生徒の得点[科目番号];
match_average += diff * diff;
}
if(best_match_average > match_average) {
best_match_average = match_average
傾向が似ている生徒 = 生徒
}
}
考え方は、これでいいのかな？
match_average は、ユークリッド距離とか平均二乗偏差を意味する数値だけど、
あえて平方根をとらないことが高速化になってるしｗ
670:デフォルトの名無しさん
10/02/15 18:34:10
>>667
問題によっては複数の支援ツールからなるソリューションパッケージは
あっても単独ソルバーアプリにまではとても出来てない問題って沢山あ
るからな
671:669
10/02/15 18:56:34
>>654
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
うｐしてみる
672:デフォルトの名無しさん
10/02/15 19:22:00
俺だったら「極座標」を使い、生徒の得点を中心からの距離と
緯度、経度とかの角度で表す。
「成績球」を半径方向と角度方向の非合同領域に分割し
生徒がどこに所属しているかで似ているかどうかを決める。
データ入力の段階で所属を決めるから、検索はデータの１回の
通読だけで至って単純。
だが領域の取り方が相当恣意的になりデータの分布が事前に
分かっていたら結果のコントロールもかなり出来るんで
敢えて書くべきコードじゃないと思うんでパス
（実際の問題では球の中に決して一様に分布しないんで
この方法は不適）
673:デフォルトの名無しさん
10/02/15 20:02:38
>672
出だしと、まとめが矛盾してるぞ？
まあ、つべこべ言わずにコードを書いてみろ。
言ってることが難しすぎて俺にはトンと理解できねえ、
どんなコードになるのか興味あるわ。
書いてください、お願いします。
674:デフォルトの名無しさん
10/02/15 20:12:17
>>670
CとかC++とかJavaがソリューション系では好かれない理由は
書くべきプログラムは音楽みたいにmainで始まりトップダウ
ンに一気に終了ってパターンであるという固定観念を印象づ
けるからじゃね？ソリューション系ではどっちかというと
「絵」とか「図」を書くに近いんで。
多くのC/C++ Javaプログラムの実際はそうではないことは
ベテランにはわかってるんだが、教育プロセスにおいて
OJTで新人に教える時にコード字面から植え付けられる先入観が
結構邪魔してると認識されることが多いんじゃないかと
675:671
10/02/15 20:25:39
>651
問題をよく読んでいなかった、データ構造を組まなきゃいけないのね。
０点だわｗｗｗ
676:デフォルトの名無しさん
10/02/15 22:13:02
>>654
類似度は得点を正規化して内積を取ったものとしている
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
677:676
10/02/15 23:03:19
>>676
一番近いものだけ分かればいいから qsort じゃなくてもよかった
678:デフォルトの名無しさん
10/02/15 23:25:17
依頼者（今回は質問者かな？）のレベルに追いついたことはわかったw
679:デフォルトの名無しさん
10/02/16 01:41:40
>>615
問題を解説してくれたまへ
ここまでで挫けた
ステップ1
double v(double x){
return 4*(pow(x, -12)-pow(x, -6));
}
v(x)==εn (但しεn=-0.75) となる二つの x を二分法で求めよ
ステップ2
ステップ1 で求めた xin xout を用いて次の積分を計算せよ
s(εn)=2*γ*∫sqrt(εn-v(x))dx
ステップ3
ステップ2 の結果を用いて n を求めよ
ステップ4
？？？
ステップ1～4 を使って γ の値を変化させ…頑張れ
680:デフォルトの名無しさん
10/02/16 01:59:58
ちょっと関係ないかもしれないんだが、今の時期って大学とか休みだから、今ある質問って何の宿題？
長期休暇とかの？それとも高校のか？
681:デフォルトの名無しさん
10/02/16 03:16:24
大学院の専門分野での研究課題や入試問題を貼ってて、その後何も反応が
無い依頼は釣りだと思って、スルーしてたんだけど(´･ω･`) ﾁｶﾞｳﾉｶﾅ？
682:デフォルトの名無しさん
10/02/16 04:12:58
>>681
？
683:デフォルトの名無しさん
10/02/16 05:08:42
[1] 授業単元：プログラミング
[2] 問題文(含コード&リンク)： URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
[3] 環境
[3.1] OS： WindowsVista
[3.2] Visual C++ 2008
[3.3] 言語： C++
[4] 期限： 2月17日まで
[5] その他の制限： 特になし
よろしくお願いします。
684:デフォルトの名無しさん
10/02/16 07:39:27
>>681
研究室レベルのものはあったが（>>615) 入試はみかけない。
685:デフォルトの名無しさん
10/02/16 08:02:15
実際に解く内容は簡単だけど
問題を理解するのが難しいｗ
686:デフォルトの名無しさん
10/02/16 08:57:46
>>684
例えば >>554 とか、プログラム作成を除けば、東京大学大学院の
入試問題↓とほとんど同じだったりするからさ。
URLﾘﾝｸ(www.i.u-tokyo.ac.jp)
普通の回答依頼かとも思ったんだが、真面目に答えて後釣り宣言されるのも
アレだから、微妙に情報系を逸脱する宿題はスルーして様子を見てることにしてる
687:デフォルトの名無しさん
10/02/16 09:58:04
>>684
>>615 は、基礎的な数値計算だろ。学部1年生レベル。
688:デフォルトの名無しさん
10/02/16 10:04:02
数式こそ長くて複雑だが、やってることは方程式の解を求めることや数値積分だ。
2分法、セカント法、シンプソン公式を使えばいい。
689:デフォルトの名無しさん
10/02/16 14:48:36
>>676
これは>654の求めてるものと違うんじゃないかな？
『使いまわしの効かない検索用情報』の収集を
フルスキャンで行っているので、力まかせの探索にしかなってないよね。
690:デフォルトの名無しさん
10/02/16 16:36:07
>>689
一応正規化した段階の情報だけは使いまわせる
691:デフォルトの名無しさん
10/02/16 17:40:44
>>654
>>676 の改造版
先に全ての生徒間の類似度を計算してみた
予め O(N^2) のコストがかかっているので、検索回数が N に比べて十分に多いときだけ有効
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
692:デフォルトの名無しさん
10/02/16 17:45:15
データ数が増えた時のパフォーマンスの低下率
条件付きUPDATE処理に置ける実更新率
こういった観点からデータ構造に見直しが入る
やりかたは一つじゃなく、データの分布に
前提条件を置くことによって、相当のパフォーマンス
改善になるが、汎用性と信頼性は犠牲になる
693:デフォルトの名無しさん
10/02/16 19:02:05
k-dimension tree の出番ですか。
694:デフォルトの名無しさん
10/02/16 20:36:27
>>693
ある範囲内をすべて列挙するのは簡単そうだけど
ある場所の近所だけを調べるってのは簡単なの？
695:デフォルトの名無しさん
10/02/17 02:44:01
C言語固有の問題では無さそう。
データベース板か数学板で聞いてからの
ほうが良さげ。てか依頼者はもう見てないのか？
696:デフォルトの名無しさん
10/02/17 03:38:52
>>654
傾向の近さの指標として相関係数を使用。gccを使用しているので、VC++では改変が必要かも。
また高速化の余地は十分あると思います。
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
697:デフォルトの名無しさん
10/02/17 05:59:24
こういう問題は、「相関度」は外部関数としてブラックボックス
として扱うんじゃね？
698:デフォルトの名無しさん
10/02/17 06:09:13
相関度に最適なデータ構造の設計も課題なのだが。
そうだ、これもブラックボックスにしよう。
699:デフォルトの名無しさん
10/02/17 06:34:49
[1] 授業単元：C++
[2] 問題文(含コード&リンク)：
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
[3] 環境
[3.1] OS： (Windows)
[3.2] コンパイラ名とバージョン： (VC8)
[3.3] 言語： (C++)
[4] 期限： ([2010年2月17日12:00まで]
非常に短い期間を設定していますがあくまで希望納期です
700:デフォルトの名無しさん
10/02/17 10:01:02
>>699
無料デバッガ募集でつか？(・∀・)ﾆﾔﾆﾔ
701:デフォルトの名無しさん
10/02/17 10:04:06
無料デバッグしてやるでつよ(・∀・)ﾆﾔﾆﾔ
m_SumList.AddTail((void*)&List1);
m_SumList.AddTailに渡すのは(void *)(CStringList **)&List1で本当にいいんでつか？
702:デフォルトの名無しさん
10/02/17 11:34:42
>699
いくらでも生じる可能性はある
それにしてもC++で(void *)とか何考えているんだ
703:デフォルトの名無しさん
10/02/17 14:03:40
funkてｗ
704:デフォルトの名無しさん
10/02/17 14:52:59
>>697
そうだね。だが難しい。相関度に適当な仮定を入れないと
無理だろ
>>698は回答として完全にナンセンスだが、それ以前に
問題も曖昧過ぎかもね。
705:デフォルトの名無しさん
10/02/17 21:09:00
[1] 授業単元：C
[2] 問題文(含コード&リンク)：URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
[3] 環境
[3.1] OS: 問わず
[3.2] Cがコンパイルできれば・・・
[3.3] 言語： C
[4] 期限： 今日
[5] その他の制限：左側の要素をしきい値としたクイックソートです．閾値と等しい場合は右側へ
お願いします
706:デフォルトの名無しさん
10/02/17 22:00:48
>>697
この問題の場合は高速で処理できることも重視されてるようだから、
ブラックボックス化しても処理速度が同等以上ならそのほうが良いけれど、
そうでなければ、どちらがいいかは一概には言えないよ。
707:デフォルトの名無しさん
10/02/17 22:32:12
>>705
今日迄というのはいくら何でも んG
708:デフォルトの名無しさん
10/02/18 16:28:57
[1] 授業単元：
期末レポート
[2] 問題文(含コード&リンク)：
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
[3] 環境
[3.1] OS： (Windows/Linux/等々)
FreeBSD バージョンは知りません
[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)
gcc バージョンは知りません
[3.3] 言語： (C/C++/どちらでも可 のいずれか)
C言語
[4] 期限： ([yyyy年mm月dd日hh:mmまで] または [無期限] のいずれか)
2月末日まで
[5] その他の制限： (どこまで習っているか、標準ライブラリは使ってはいけない等々)
C言語どころか、UNIXマシンの操作もおぼつきません。急ぎませんので
片付けて頂ければうれしいです
709:デフォルトの名無しさん
10/02/18 17:06:42
>>708
int binarycopy(FILE *, FILE *);
int main(int argc, char **argv){
FILE *src, *dest;
if (argc != 3) return -1;
src = fopen(argv[1], "rb");
if(src == NULL) {
fprintf(stderr, "%s が開けない\n", argv[1]);
return -1;
}
dest = fopen(argv[2], "wb");
if (dest == NULL) {
fprintf(stderr, "%s が作成できない\n", argv[2]);
return -1;
}
if(!binarycopy(src, dest)) {
remove(argv[2]);
fprintf(stderr, "複製に失敗\n");
return -1;
}
fclose(src);fclose(dest);
return 0;
}
710:デフォルトの名無しさん
10/02/18 17:07:25
>>708 続き。
int binarycopy(FILE *s, FILE *d) {
#define BUFFSIZE 256
char buff[BUFFSIZE], size = sizeof (char);
size_t n = 0, total = 0, buffsize = BUFFSIZE;
#undef BUFFSIZE
for (;;) {
n = fread(buff, size, buffsize, s);
n = fwrite(buff, size, n, d);
total += n;
// エラーが生じた場合や、end-of-file(ファイルの最後)に達した場合、
// 返り値は指定した個数よりも小さい値(またはゼロ)となる。
if (n == 0 || n < buffsize) break;
}
return total;
}
711:デフォルトの名無しさん
10/02/18 21:35:42
>>699
いｆ（ｐぃｓｔ２）｛
POSITION pos2 = plist1->GetHeadPositon();
CString str = plist1->GetNext(pos2);
｝
712:デフォルトの名無しさん
10/02/18 21:37:02
>>711
ｐぃｓｔ２じゃねーや１だ
713:デフォルトの名無しさん
10/02/19 15:26:05
HPはどのページも3クリック以内でたどり着けるのが良いとされています。
さて問題です。どのページからも、すべてのページへこの条件を満たすようにするには
各ページにリンクはいくつ必要でしょうか。
link(n)をページnのリンク数としたとき min { link(n) } を決定するという問題です。
714:713
10/02/19 15:27:42
ページ数は、1000から1万の任意の値が与えられる物とします。
715:デフォルトの名無しさん
10/02/19 15:38:17
min(Σlink(n))じゃなくて？
インデックスページを作り、
他のページはインデックスページへ1つのリンクを持てば
どのページへも2クリックで行けるから
min(link(n))はインデック以外のページすべて=1
716:デフォルトの名無しさん
10/02/19 15:43:44
∩★テンプレに即していないんで★雑談扱いとさせて頂きます★∩
717:デフォルトの名無しさん
10/02/19 15:53:55
min(max(link(n)))
718:デフォルトの名無しさん
10/02/19 15:59:21
ページのリンクの最大数を、最も小さくするようにするってことでした。
719:デフォルトの名無しさん
10/02/19 16:03:43
面白いけど奥深すぎ
720:デフォルトの名無しさん
10/02/19 17:16:00
>>654
クラスタリング k-meansでググれ
721:デフォルトの名無しさん
10/02/20 01:10:58
>>713
ページ数Nに対して 2√N くらいじゃないかね
戦略：
・全部のページを同じ大きさのm個のグループに分ける(各グループには N/m ページある）
・各グループにインデックスページを作り、
グループ内の他の全てのページと相互リンクする
・各グループのインデックスページを全て相互リンクする
・任意の2ページ間は多くても
自グループのインデックス→目標グループのインデックス→目標ページ
の3クリックで移動できる
一番リンクの数が多いのは各グループのインデックスページで、
max(link(n)) = (インデックス間の全結合) + (グループ内のリンク） ≒ m + N/m
これが最小になるのは m=√N のときで min(max(link(n))) ≒ 2√N
722:デフォルトの名無しさん
10/02/20 01:29:14
>>721を書いてから半分にできることに気づいた
戦略：
・全部のページを同じ大きさのm個のグループに分ける
・グループ内のページは全て相互リンクする
・グループ内の(m-1)個のページにそれぞれ担当のグループを割り当て、
グループ間の担当のページ同士を相互リンクする
・任意の2ページ間は多くても
自グループの担当ページ→目標グループの担当ページ→目標ページ
の3クリックで移動できる
このとき、リンクの数が一番多いのはグループ間を繋ぐ担当のページで、
max(link(n)) = (グループ内の全結合） + （担当グループへのリンク） = N/m-1 + 1
最も効率が良くなるのは、グループ内の全てのページが他のグループの担当ページになるとき、
つまり N/m = m のときで、そのときm = √Nであって、 min(max(link(n))) = √N。
723:デフォルトの名無しさん
10/02/20 01:41:52
独り言を書くのは俺も含めて勝手だが...
>一番リンクの数が多いのは...
と勝手に決めて、それが最小になるのは...
とする論法は頂けませんなw
希望的見積もりというのなら分かるが...
このスレで常連回答者やってる人どんな質問にも
答えがあって、答えなければいけないんだと
思い込む空気が醸成されておりそれに毒されてしまっ
てるかもしれないことに常に気をつけなければならないね。
プログラミングの場合は、数学の問題と違って
必ずしも正解があるとは限らない対象も扱わざるを得ない
場合が多くて大変だからこそ...
724:722
10/02/20 01:51:03
>>723
>>一番リンクの数が多いのは...
>と勝手に決めて、それが最小になるのは...
>とする論法は頂けませんなw
ごめんなさいごめんなさい。>>721の勢いで適当なこと書きました。
ちゃんと計算したら max(link(n)) ≒ N/m + m/(N/m) で、
min(max(link(n)) ≒ 1.89*(N)^(1/3) くらいでしたorz
というかC/C++の宿題じゃないな、その点についても謝る
725:デフォルトの名無しさん
10/02/20 01:56:24
論点がずれてた件…
「この戦略のもと」ってちゃんと書かないといけないな
採った戦略が厳密に最適かは分からんが、
それでも準最適な戦略を考え出すのがプログラムに必要な能力
726:デフォルトの名無しさん
10/02/20 02:03:49
>>713
最適解かどうかは不明だけど、実現可能な解
#include<stdio.h>
#include<stdlib.h>
int max_min(long n)
{
long i, j;
if(n==1) return 0;
if(n<=4) return 1;
for(i=0;;i++)
{
for(j=1;j<=i;j++)
{
if(j*(i-j+1)*(i+1)+j>=n) return i;
}
}
return -1;
}
int main(int argc, char *argv[])
{
int n=1000;
if(argc==2) n=atoi(argv[1]);
printf("%d\n", max_min(n));
return 0;
}
727:726
10/02/20 02:32:46
>>726
間違ってたorz
728:デフォルトの名無しさん
10/02/20 02:53:03
頭の中のハイパーリンクも含めたらそうなるなw
729:726
10/02/20 03:03:20
>>713
これで実現可能になった…はず
#include<stdio.h>
#include<stdlib.h>
int max_min(long n){
long i, j;
if(n==1) return 0;
if(n<=4) return 1;
if(n<=7) return 2;
for(i=2;;i++){
for(j=2;j<=i;j++){
if(j*(i-j+1)*(i-j+1)+j>=n){
return i;
}
}
}
return -1;
}
int main(int argc, char *argv[]){
int n=1000;
if(argc==2) n=atoi(argv[1]);
printf("%d\n", max_min(n));
return 0;
}
730:デフォルトの名無しさん
10/02/20 03:23:33
正解と汚解ってかW
>>555に対する>>570とかの解答とかな
731:デフォルトの名無しさん
10/02/20 04:06:13
>>615
URLﾘﾝｸ(codepad.org)
γ=100を計算するところまで。解析解との比較は面倒だからやってない。
x_in、x_outが単調に増減してるからそんなに間違ってないはず。
γ変えて議論するのは自分でやってくれ。γは128行目
732:デフォルトの名無しさん
10/02/20 04:54:56
スレ違いだけど解きたくなっちゃうのは仕方ないよな
733:デフォルトの名無しさん
10/02/20 05:01:57
解くべきはまずはその問題の出所。というよりも問題意識に共感できること。
そして実は対象に問題はなく真の問題は解きたいと思う汝自身に発している
かも知れないということも考えると間違いは少ない。
以上チラ裏
734:デフォルトの名無しさん
10/02/20 06:13:09
>>713
ｽﾚﾘﾝｸ(tech板:740番)
735: ◆/91kCCQXBo
10/02/20 10:52:17
ｽﾚﾘﾝｸ(tech板:739番)
#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*(n-1))%m+1 );
}
}
puts(""); return 0;
}
736: ◆/91kCCQXBo
10/02/20 11:05:35
なんか、今見たら違ってる。
737: ◆/91kCCQXBo
10/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:デフォルトの名無しさん
10/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
10/02/20 14:50:48
>>722 のアルゴリズムじゃねーｗ
740:デフォルトの名無しさん
10/02/20 21:27:37
実際にリンク組んで確かめるプログラムはないんですか。
741:デフォルトの名無しさん
10/02/20 23:30:28
ていうか、あってるかどうか確認するプログラムって、オーダはどうなる？
ページ数をN、最大クリック数をCとしたら、NCでできるのか？
742:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/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:デフォルトの名無しさん
10/02/21 00:57:26
ヒューリスティックアプローチを探したいものだが
C/C++言語ではやめたほうがいいかも
VM上で実行できる処理系でないと
カーネルコードが書ける処理系ではお勧め出来ない
745:738
10/02/21 02:02:28
>>738 のアルゴリズムで解いた結果は
総ページ数 1000 のとき、最大リンク数 18
総ページ数 10000 のとき、最大リンク数 40
合ってるかどうか未確認
詳細内容 50kB
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
746:デフォルトの名無しさん
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