- プログラミングのお題スレ Part7 [転載禁止]©2ch.net
481 ：デフォルトの名無しさん[sage]：2015/07/25(土) 17:23:05.26 ID:5K8h4x4y - 当然ポインタからアドレス値を得ることもNGだよな
ポインタは異なることが識別できれば良いだけの
内部情報で、不定長さビットストリームと仮定
| - プログラミングのお題スレ Part7 [転載禁止]©2ch.net
482 ：デフォルトの名無しさん[sage]：2015/07/25(土) 17:25:54.14 ID:5K8h4x4y - 辿れることは仮定
循環があればリスト要素数は∞とカウントされるんで
少ないメモリ領域とやらのサイズをリスト要素サイズで割った値を
超えたら循環が発生してるんだろうね。
本当問題にもならない
| - プログラミングのお題スレ Part7 [転載禁止]©2ch.net
484 ：デフォルトの名無しさん[sage]：2015/07/25(土) 17:28:38.67 ID:5K8h4x4y - B木などのように分岐する木の場合は、辿る時は
段を設定しそれを超えたらまだ伸びていても再帰
呼び出しから復帰。段を増やしながら辿利直す
| - プログラミングのお題スレ Part7 [転載禁止]©2ch.net
489 ：デフォルトの名無しさん[sage]：2015/07/25(土) 18:02:07.17 ID:5K8h4x4y - メモリ領域のサイズ取得が不可能な場合
辿れる（＝ノードの分岐数に上限を設定できる）
という前提からほぼ線形リストを前提とできる。
循環があれば、循環の（リスト先頭からみた）先頭と
循環周期の組(h,c)が決まる筈
(h,c)=(0,1)(0,2)(0,3)....(1,1),(1,2)...(2,1),(2,2),...のどれか
例
(h,c)=(2,3)
先頭から見て２番目の要素が周期3の循環を持つ
(m,n)であるかどうかのチェックは簡単なコードで
配列とか必要とせずに書ける。
h+c=1 となる有限の組み合わせに対してチェックし...
h+c=2 となる有限の組み合わせに対してチェックし...
h+c=3 となる有限の組み合わせに対してチェックし...
....
効率とか無視したらこんな感じかな？
| - プログラミングのお題スレ Part7 [転載禁止]©2ch.net
492 ：デフォルトの名無しさん[sage]：2015/07/25(土) 18:16:11.40 ID:5K8h4x4y - (m,n)かどうかのチェックコード
NILリスト終端を表すリスト
LIST_HEAD:リスト先頭
戻り:1循環あり,0:循環なし
int chk(int m,int n){
list *p=LIST_HEAD,*q;
int i;
for(i=0;i<m;i++){
p=p->next;
if(p==NIL)return 0;
}
for(q=p->next,i=0;i<n;i++,q=q->next){
if(q==NIL)return 0;
if(q==p)return 1;
}
return 0;
}
周期の定義のしかたでちょっと変わる
かもしれないがこんな感じか
| - C/C++の宿題片付けます 169代目 [転載禁止]©2ch.net
525 ：デフォルトの名無しさん[sage]：2015/07/25(土) 18:26:49.66 ID:5K8h4x4y - ｋｗｓｋ
|
|