しりとり 無限ループ？
- 最長の結果が１０個程度の時は期待通りに動作します期待される結果が２０程度になると(?)timeoutします単にウチのマシンじゃムリなのか、工夫が足りないのか無限ループを起こしてるのか、重いだけなのか判断つきません
- 問題やってるんですが処理がtimeoutしちゃいました最長の結果が１０個程度の時は期待通りに動作するんですが、期待される結果が２０程度になるとtimeoutします
- 問題を解いているのですが、最長の結果が10個程度の時は問題なく動作しますが、20個程度の結果が期待される場合にtimeoutしてしまいます。自分のマシンが限界なのか、改善ポイントがあるのか、無限ループを起こしているのか、重いだけなのか分かりません。
- ベストアンサー
しりとり 無限ループ？
【予約語から最長のしりとりを作ろう！】 https://codeiq.jp/ace/stakemura/q408 この問題やってるんですが 処理がtimeoutしちゃいます 最長の結果が１０個程度の時は期待通りに動作します 期待される結果が２０程度になると(?)timeoutします 単にウチのマシンじゃムリなのか、工夫が足りないのか 無限ループを起こしてるのか、重いだけなのか判断つきません よろしくお願いします （cpp11_keywords.csvはC++の予約語84個のcsvです） <?php $data=explode(chr(10),file_get_contents('cpp11_keywords.csv')); foreach($data as $i=>$cpp){$data[$i]=trim($data[$i]);} echo(implode('<br/>',createSiritori($data))); function createSiritori($words){ $rtn=array(); $data=array(); for($i=0,$len=count($words);$i<$len;$i++){ $data[$i]=array(); for($j=0;$j<$len;$j++){ if($i==$j)continue; if(is_connectable($words[$i],$words[$j]))$data[$i][]=$j; } } $rcd=0; for($i=0;$i<$len;$i++){ $crr=array($i); for($j_arr=array(0),$j_ind=0,$len_arr=array(count($data[$i]));$j_arr[0]<$len_arr[0];$j_arr[$j_ind]++){ if($j_arr[$j_ind]>=$len_arr[$j_ind]){ array_pop($crr); array_pop($j_arr); array_pop($len_arr); $j_ind--; }else if(!in_array($data[end($crr)][$j_arr[$j_ind]],$crr)){ $crr[]=$data[end($crr)][$j_arr[$j_ind]]; $j_ind++; $j_arr[$j_ind]=0; $len_arr[$j_ind]=count($data[end($crr)]); if($j_ind>$rcd){$rcd=$j_ind;$rtn=$crr;} } } } for($i=0,$len=count($rtn);$i<$len;$i++){ $rtn[$i]=$words[$rtn[$i]]; } return $rtn; } function is_connectable($a,$b){ return (substr($a,-1)==substr($b,0,1)); }
- H240S18B73
- お礼率60% (78/128)
- PHP
- 回答数9
- ありがとう数8
- みんなの回答 （9）
- 専門家の回答
質問者が選んだベストアンサー
このプログラムだと、 例えば ab bc cd というテキストだった時、最後のcdが出力されないし、 cd bc ab だった時、bcから始まっちゃいます。(正解はabのはず) どうやらこのロジックだと、1行目の単語に、次に紐付く単語が あると、必ず1行目の単語から始めてしまいますね。 （1単語ずつしりとりを行って、最長しりとりが行われた パターンについて出力しているのではない？） ちなみにここまでは出るようですよ。enumの後で止まるので、 それ以降、条件に合致せず無限ループに陥っているのでは。 alignas short this signed default throw while explicit true export typedef friend delete extern noexcept typeid do or return nullptr reinterpret_cast typename enum
その他の回答 (8)
- duke_kimura
- ベストアンサー率39% (53/134)
なんか面白そうなサイトですね。 不正解答は駄目のようなのでアルゴリズムはさておき、 これをphpで組むならまずはデバッガ(トレーサ)を入れるところからやるべきかと思います。 XDEBUG
- 参考URL：
- http://xdebug.org/
お礼
ありがとうございます しかし、こういう遊びにしろDreamweaverとMAMPという環境下で出来る事の範囲を広げたり、あるいはこの環境の限界を知ったりその対応方法を考えるということが一つの目的なので環境を変えるということはないかと思います、スイマセン
- Yune-Kichi
- ベストアンサー率74% (465/626)
大元の問題で「timeoutする」とありましたが，これに関しては，CLI使えばタイムアウト「は」しなくなりますよ。 つまり，terminalなりコマンドプロンプトなりから， php ファイル名 で実行すると，echoした内容はそのまま標準出力に書き出されます。 # 改行は定数PHP_EOLを出力して下さい。 PHPでアルゴリズム系の話をするなら，サーバー使うよりもCLIでやった方がわかりやすそうに思えます。
お礼
どうやら無限ループを起こしてるようなので 無謀なことはやめておきます（笑）
- めとろいと（@naktak）
- ベストアンサー率36% (785/2139)
これ何個でるのが答えなんですかねーー。 挑戦してみないと分からないのでしょうけど・・・。 C#で作ってみたら、正しいかどうかはさておき、最長29で、一瞬で返ってきました。 (一瞬すぎるから不正解なのかな？) もともと処理しまくるものというのが拍車をかけて、めっちゃループしてる処理が 何をしようとしているのかすぐに読み解けない作りなので、ちょっと追えませんね。 色々書くと怒られそうだったので、簡単なヒントを出すと ・しりとりとは先頭文字と末尾文字が必ず紐付いている。 ・先頭文字や末尾文字が同じものが複数ある。 ・もしかしたら逆引き(しりとりが終わる単語から遡る)のが楽かも？ 後から気づいたので、私は試してません。 こんなものでしょうか。
お礼
基本的な処理の流れとしては １、各単語に後続しうる単語の番号を配列に記録 ２、先頭の単語の番号を前から順に一時配列にいれ そこから後続しうる単語の番号をまた順にいれ 最大長であれば戻り値候補として記憶 後続しうる単語がなくなったら一時配列の末尾を除き 一つ前の単語の後続候補を次に進める これを先頭の単語が８４個全部巡るまで続ける ３、戻り値の単語番号を単語に戻す というような流れです 基本的にはしりとりが成立しうる組み合わせしか 試行しないので答えが短ければいくんですけどね…
- bm_hiro
- ベストアンサー率51% (200/388)
とりあえず、ソースは読んでいないのだけど・・・ 84種類を 一個づつ 減らしながらかけていったらー 3.3142401345654E+126 うん。天文学的数字になりました。 まぁ、ヒントも出ちゃってるし、当たり前過ぎるだし、この程度なら言っても差し支えないかなと思うので言うと、最初の一文字で分類するのがいいんじゃない？
お礼
うん、ムリだ（笑）
処理の遅いPHP言語で総当たりは非現実的すぎますね・・・ C言語でも結構厳しいと思います。 一応 for → foreach 欲しいものを値にとる配列 + in_array → 欲しいものをキーにとる配列 + isset などまだまだソースコード実行を速められる余地があります。
お礼
ありがとうございます まあでも多分チューニングしてどうにかなるレベルじゃないですよね（笑）
- kmee
- ベストアンサー率55% (1857/3366)
こういうのは、総当たりでやってたら、物凄い勢いで処理回数が増えていきます。 「組み合わせ爆発」と言われています。 確かに、遅いマシンでは遅いですが、このような問題では、多少マシンを速くしたところで焼け石に水です。 なので、アルゴリズムを工夫して、無駄をいかに省くか、というのがコツになります。 なんとか無駄な選択肢を減らせないか、を考えましょう。 ところで、そのサイトに > 解答送信の有無を問わず、模範解答のネタばれにつながるような各種行為、別人による不正解答は、固くお断り申し上げます。 とあるのですが、大丈夫でしょうか?
お礼
多分、模範解答には全くならないので大丈夫です（笑） 回答としても、コード自体は間違っていないか 無限ループを起こすようなことにはなっていないか この程度ならマシンスペックとかPHPの設定とかでどうにかなるレベルか それともこのやり方ではスパコンつかってもムリなレベルなのか その辺の回答をいただきたいと思っています 無駄な選択肢を減らす工夫、考えてみます ありがとうございます
- めとろいと（@naktak）
- ベストアンサー率36% (785/2139)
for($j_arr=array(0),$j_ind=0,$len_arr=array(count($data[$i]));$j_arr[0]<$len_arr[0];$j_arr[$j_ind]++){ このループをめっちゃ繰り返してますね。 ソースは追ってません。 各ループ直後でechoしたら上記ループが大量でした。
お礼
はい 単純にしりとりが成立する組み合わせを総当たりしているので 最悪全ての単語が互いにしりとり連結可能な場合 84!通りを総当たりする事になります さすがにそれはないにしろ 多分、半分以上の単語を使用したしりとりが成立し 5^45ぐらいはループすることに なるだろうと予想しています （一度100万ループぐらいで止めてみましたが 予想される処理全体の0.01%も進んでませんでした）
関連するQ&A
- 配列の次元を超えてランダムに選択したい
PHP5.2.4を使用しています。 例えば、次のような2次元以上の配列があったときに $arr[0][0] = array('a' => 1, 'b' => 11); $arr[0][1] = array('a' => 2, 'b' => 5); $arr[0][2] = array('a' => 3, 'b' => 20); $arr[1][0] = array('a' => 4, 'b' => 3); $arr[1][1] = array('a' => 5, 'b' => 30); この5つから、'b'の値が10以上の候補だけのインデックス（$arr【[1][1]】←この部分）を ランダムに1つ選ぶ方法はどのようになるのでしょうか？ 自分が考えたのは for ($i = 0; $i < count($arr); $i++) { for ($j = 0; $j < count($arr[$i]); $j++) { if ($arr[$i][$j]['b'] < 10) continue; $new_arr[] = array('index2' => $i, 'index1' => $j); } } $key = array_rand($new_arr, 1); print_r($new_arr[$key]); //Array ( [index2] => 0 [index1] => 0 ) //Array ( [index2] => 0 [index1] => 2 ) //Array ( [index2] => 1 [index1] => 1 ) //いずれかが選択される なんですが、これだとあまり良いやり方だと思わなくて なにか別のやり方はあるのでしょうか？
- 締切済み
- PHP
- PHPに関する質問です。
PHPに関する質問です。 データベースからfetchしたデータを 10件づつとりだしグループ化して、最後の残りが8件以下の場合は、各グループの配列の先頭に加えるという処理を行う際に、このような記述をしているのですが、 $data = array(); // 保存する配列 $ct1 = 0; $ct2 = 0; while($row = $res->fetch(PDO::FETCH_NUM)) { if ($ct2 === 10) { $ct1++; $ct2 = 0; } if ($ct2 === 0) { $data[$ct1] = array(); } $data[$ct1][] = $row; $ct2++; } if (count($data[$ct1]) < 8) { $arr = array_pop($data); $x = floor(count($arr) / count($data)); // 各要素に割り当てる数 for ($i = 0; $i < count($data); $i++) { for ($j = 0; $j < $x; $j++) { array_push($data[$i], array_pop($arr)); } } $t = 0; while (count($arr) > 0) { // 最後のあまりを先頭に追加 array_push($data[$t], array_pop($arr)); $t++; } } この処理だと、生成された配列が３次元になってしまいます。 Array ( [0] => Array ( [0] => Array ( [0] => あ ) [1] => Array ( [0] => あ) [2] => Array ( [0] => あ) [3] => Array ( [0] => あ) [4] => Array ( [0] => あ) [5] => Array ( [0] => あ ) [6] => Array ( [0] => あ ) [7] => Array ( [0] => あ) [8] => Array ( [0] => あ ) [9] => Array ( [0] => あ ) [10] => Array ( [0] => あ) ) [1] => Array ( [0] => Array ( [0] => あ) [1] => Array ( [0] => あ) [2] => Array ( [0] =>あ ) [3] => Array ( [0] => あ ) [4] => Array ( [0] => あ ) [5] => Array ( [0] => あ ) [6] => Array ( [0] => あ) [7] => Array ( [0] => あ ) [8] => Array ( [0] => あ ) [9] => Array ( [0] => あ ) [10] => Array ( [0] => あ ) ) [2] => Array ( [0] => Array ( [0] => あ ) [1] => Array ( [0] => あ) [2] => Array ( [0] => あ ) [3] => Array ( [0] => あ ) [4] => Array ( [0] => あ) [5] => Array ( [0] => あ ) [6] => Array ( [0] => あ ) [7] => Array ( [0] => あ ) [8] => Array ( [0] => あ ) [9] => Array ( [0] => あ) [10] => Array ( [0] => あ ) ) [3] => Array ( [0] => Array ( [0] => あ ) [1] => Array ( [0] => あ ) [2] => Array ( [0] => あ ) [3] => Array ( [0] => あ ) [4] => Array ( [0] => あ ) [5] => Array ( [0] => あ) [6] => Array ( [0] => あ ) [7] => Array ( [0] => あ ) [8] => Array ( [0] => あ ) [9] => Array ( [0] => あ) ) ) これを array([0]=>array(あ,あ,あ,あ,あ,あ,あ)[1]=>array(あ,あ,あ,あ,あ,あ,あ)) のように２次元で取り出すには、どのように行えばいいでしょうか。 この後の処理としては、 $key = 'a'; array_search（$key,$data） のようにキーを取得したいと考えています。 宜しくお願いします。
- 締切済み
- PHP
- n-gramの手直し
プログラミング歴３週間ですが、n-gramのプログラミングを 作ってみましたが、うまく動きません。結果が「可愛い」 「あの子」「デートしたい」とならないといけないののですが、 どなたか優秀な方に手直しをお願いしたいと思います。よろしく お願いいたします。 my $a = "可愛いあの子とデートがしたい"; my $b = "あの子可愛いよね。デートがしたい"; $len1 = length($a); $len2 = length($b); my $i = 0; while($i < $len1) { if (0 == ($i % 2)) { $re1 = substr($a, $i, 2); my $j = 0; while($j < $len2) { if(0 == ($j % 2)) { $re2 = substr($b, $j, 2); } $j++; if($re1 eq $re2) { @word1 = ("$re1"); $num1 = push(@words, @word1); $count++; last; } } } $i++; if(0 == ($i % 2)){ if($re1 ne $re2){ if($count > 0) { @word2 = ("\n"); $num2 = push(@words, @word2); $count = 0; } } } } my $rewords = join('', @words); print $rewords;
- ベストアンサー
- Perl
- 割り切れなくなるまで分割して配列に入れたい
<?php make(7); function make($n) { $arr = array($n); $arr_new = division_arr($arr); print_r($arr_new); } function division_arr($arr) { for ($i = 0; $i < count($arr); $i++) { $arr_new[$i] = division($arr[$i]); if ($arr_new[$i][0] > 0) { return division_arr($arr_new[$i]); } else { } } return $arr_new; } function division($n) { $a = $b = floor($n / 2); if ($n % 2 != 0) { $b+=1; } return array($a, $b); } /* array( [3,4], [[1,2],[2,2]], [[0,1],[1,1],[1,1],[1,1]] ); 再帰的に配列を分割していき、最終的にこのような出力にしたいです。 */ ?> 教えて下さい。よろしくお願いいたします。m(_ _)m
- ベストアンサー
- PHP
- 二次配列のqsort
二次配列のqsortについて分かる方に教えて頂きたいのですが 一段落のプログラムを載らせていただきました．count3[j][i]をバブルソートで降順でやってみましたが高速が要求されるため,qsortを使ってやり直したいのですが （ちなみにcount1[j][i],count2[j][i]は前で定義してあります．count4[j][i]にはiの順番を記憶するための二次配列です） ぜひともよろしくおねがいします． int ind_near_search(int j,int t) { int i,var_num,count3[IND][VAR],count4[IND][VAR],temp1,temp2,num=0,m=0; for(i=0;i<VAR;i++){ if(individual[j].x[i]==1){ //変数が１と０の場合分け count2[j][i]=t-count[j][i]; }else{ count2[j][i]=count[j][i]; } if(individual[j].x[i]==1){ //全てcount3に値を入れる count3[j][i]=count2[j][i]; }else{ count3[j][i]=count[j][i]; } } for(i=0;i<VAR;i++){ count4[j][i]=num++; } for(m=0;m<VAR-1;m++){ for(i=0;i<VAR;i++){ //バブルソートにより降順に並べ換え if(count3[j][i]<count3[j][i+1]){ temp1=count3[j][i]; count3[j][i]=count3[j][i+1]; count3[j][i+1]=temp1; temp2=count4[j][i]; //count4にはcount3の並べ替え後の対応する番号を入れる count4[j][i]=count4[j][i+1]; count4[j][i+1]=temp2; } } } for(i=0;i<VAR;i++){ var_num=count4[j][i]; //count4の大きい順番からその番号をvar_numに渡す if(individual[j].x[var_num]==0){//0と1の場合分け individual[j].x[var_num]=1; }else{ individual[j].x[var_num]=0; }
- 締切済み
- C・C++・C#
- ループ処理でシンプルにまとめる方法を教えてください。
（例） for ($j=0;$j<=count($arGroup)-1;$j++){ for ($i=0;$i<=count($arGroup[$j])-1;$i++){ if($j == 0){ echo "(".$number[0][$i+(count($ar)-1)].")\n"; }elseif($j == 1){ echo "(".$number[0][$i+(count($ar)-1)+(count($arGroup1))].")\n"; }elseif($j == 2){ echo "(".$number[0][$i+(count($ar)-1)+(count($arGroup1))+(count($arGroup2))].")\n"; }elseif($j == 3){ echo "(".$number[0][$i+(count($ar)-1)+(count($arGroup1))+(count($arGroup2))+(count($arGroup3))].")\n"; } } } このループ処理をもっとシンプルにしていきたいと思います。 jの数が増えていく予定)+(count($arGroup数字))が追加されていくような形になります。 どなたか教えてください。
- ベストアンサー
- PHP
- array_reverse()の使い方について
array_reverse() の使い方が分かりません・・・。 CSV（降順）のデータを読み込んでPHPで表示する仕組みを作っています。 そのCSVを昇順にしたく、array_reverse() を使っても、思うようにデータが表示されません。 CSV（data.csv）は以下の通りです。価格で降順になっているものです。 line0,line1,line2 1,ぶどう,200(円) 2,なし,150(円) 3,りんご,100(円) 4,バナナ,80(円) 5,みかん,50(円) PHPは以下の通りです。 <?php $Data=file('/data.csv'); $j=0; for($i=0;$i<sizeof($Data);$i++){ $line=explode(",",$Data[$i]); if($j<3 ){ echo $line1 $line2.' <br />'; $j++; } } ?> $Data を 昇順にしたいので（もともとのCSVを昇順で作ることはできません）、 array_reverse($Data) をどこかに入れたらいいと思うのですが、forの前、後ろといろいろ入れてみたのですが、思ったように表示がされず困っています。 お力おかしください!!!よろしくお願いします。
- ベストアンサー
- PHP
- forで無限ループになっていないかどうか
各アイテムの最新3件だけデータベースに残したいと思い、下記のようにしてみました。 動作を確認したところ問題なかったのですが、何か（無限ループする可能性があるなど）問題があるようでしたら、ご指摘いただけないでしょうか。 よろしくお願いいたします。 for ($num = 1; $num < 21; $num++){ // アイテムが20件ある場合 $sql = "SELECT COUNT(id) AS cnt FROM item where item_id=$num ;"; $res = mysql_query($sql, $conn) or die; $row = mysql_fetch_array($res, MYSQL_ASSOC); $count = $row["cnt"]; if($count<3){ // アイテムが3件より少なかったら何もしない } else{ $delete_count=$count-3; $sql = "delete from item where item_id=$num order by date limit $delete_count;"; $res = db_query($sql, $conn); } }
- ベストアンサー
- PHP
- C++の無限ループを解決してください
アルゴリズムを勉強するときに以下のソースを書きました； void weighted_quick_union_algorithm() { static const int volume = 10; enum status { terminate_, union_, find_ }; string str; status sta; vector<int> system(volume, 0); vector<int> size(volume, 1); for (int index = 0; index != volume; ++index) { system[index] = index; } do { cout<<"cin"<<endl; cin >> str; for (string::size_type index = 0; index != str.size(); ++index) str[index] = toupper(str[index]); if (str == "UNION") sta = union_; else if (str == "FIND") sta = find_; else if (str == "TERMINATE") sta = terminate_; switch (sta) { case(0): { cout << str << endl; break; } case(1): { cout << str << sta << endl; int p(0), q(0), i(0), j(0); while (cin >> p) { cin >> q; for (i = p; i != system[i]; i = system[i]); for (j = q; j != system[j]; j = system[j]); if (i == j) continue; if (size[i] < size[j]) { system[i] = j; size[j] += size[i]; } else { system[j] = i; size[i] += size[j]; } cout << p << " - " << q << endl; } cout<<"break"<<endl; break; } case(2): { cout << str << sta << endl; break; } } } while (sta); } しかし unionを入力しあと ; でwhile(cin>>p)をブレイクしたら cin break UNION1 cin break Union1 で無限ループ 結構時間かかったが間違いがわかりません ちなみに最少は while(cin>>p>>q)と書いていましたが同じ結果です。 どうかお願いします
- ベストアンサー
- C・C++・C#
- Ｃ言語 ソートについて
#include <stdio.h> #include <stdbool.h> #define NUM_ARRAY 4 #define NUM_DATA 5 int count_swap = 0; // 交換回数 int count_comparison = 0; // 比較回数 void selection_sort(int a[], int n) { } int main(void) { int data[NUM_ARRAY][NUM_DATA] = {{9, 7, 5, 6, 8}, {9, 8, 7, 6, 5}, {5, 6, 7, 8, 9}, {5, 6, 8, 7, 9}}; for (int i = 0; i < NUM_ARRAY; i++) { count_swap = 0; count_comparison = 0; int d[NUM_DATA]; copy_array(data[i], d, NUM_DATA); // 配列のコピー printf("----------------\n"); print_array(d, NUM_DATA); // ソート前の配列の表示 selection_sort(d, NUM_DATA); // 挿入ソートの実行 print_array(d, NUM_DATA); // ソート後の配列の表示 printf("比較回数: %d\n", count_comparison); // 比較回数の表示 printf("交換回数: %d\n", count_swap); // 交換回数の表示 } } 上の雛形を使って選択ソートを実行するという問題なのですが途中までそれっぽいのは出来たのですが上手くいかないので解答をお願いします。 下に自分が今書いているものを置いておきます。 #include <stdbool.h> #include <stdio.h> #define NUM_ARRAY 4 #define NUM_DATA 5 int count_swap = 0; int count_comparison = 0; void swap(int d[], int i, int j) { count_swap += 1; printf("swap a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]); int temp = d[i]; d[i] = d[j]; d[j] = temp; } void copy_array(int *a, int *b, int n) { for (int i = 0; i < n; i++) { b[i] = a[i]; } } void print_array(int d[], int n) { for (int i = 0; i < n; i++) { printf("%d ", d[i]); } printf("\n"); } bool compare(int d[], int i, int j) { count_comparison += 1; printf("compare a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]); if (d[i] > d[j]) { return true; } else { return false; } } void selection_sort(int d[], int n) { int min; for (int i = 0; i < n - 1; i++) { min = i; for (int j = i + 1; j < i; j++) { if (compare(d, min, j)) { min = j; } } swap(d, i, min); print_array(d, n); } } int main(void) { int data[NUM_ARRAY][NUM_DATA] = { {9, 7, 5, 6, 8}, {9, 8, 7, 6, 5}, {5, 6, 7, 8, 9}, {5, 6, 8, 7, 9}}; for (int i = 0; i < NUM_ARRAY; i++) { count_swap = 0; count_comparison = 0; int d[NUM_DATA]; copy_array(data[i], d, NUM_DATA); // 配列のコピー printf("----------------\n"); print_array(d, NUM_DATA); // ソート前の配列の表⽰ selection_sort(d, NUM_DATA); // 挿⼊ソートの実⾏ print_array(d, NUM_DATA); // ソート後の配列の表⽰ printf("⽐較回数: %d\n", count_comparison); // ⽐較回数の表⽰ printf("交換回数: %d\n", count_swap); // 交換回数の表⽰ } }
- ベストアンサー
- C・C++・C#
お礼
他のもの作ってて見直せてないですが どうやらやり方以前にコード自体にも 問題があることを見つけてくれたのでBA
補足
コードに問題がありましたか… 自分でもちょっと混乱して処理を 追いきれなくなってました あらためて見直してます