![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
【予約語から最長のしりとりを作ろう!】
https://codeiq.jp/ace/stakemura/q408
この問題やってるんですが
処理がtimeoutしちゃいます
最長の結果が10個程度の時は期待通りに動作します
期待される結果が20程度になると(?)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));
}
No.8ベストアンサー
- 回答日時:
このプログラムだと、
例えば
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
No.9
- 回答日時:
なんか面白そうなサイトですね。
不正解答は駄目のようなのでアルゴリズムはさておき、
これをphpで組むならまずはデバッガ(トレーサ)を入れるところからやるべきかと思います。
XDEBUG
参考URL:http://xdebug.org/
ありがとうございます
しかし、こういう遊びにしろDreamweaverとMAMPという環境下で出来る事の範囲を広げたり、あるいはこの環境の限界を知ったりその対応方法を考えるということが一つの目的なので環境を変えるということはないかと思います、スイマセン
No.6
- 回答日時:
これ何個でるのが答えなんですかねーー。
挑戦してみないと分からないのでしょうけど・・・。
C#で作ってみたら、正しいかどうかはさておき、最長29で、一瞬で返ってきました。
(一瞬すぎるから不正解なのかな?)
もともと処理しまくるものというのが拍車をかけて、めっちゃループしてる処理が
何をしようとしているのかすぐに読み解けない作りなので、ちょっと追えませんね。
色々書くと怒られそうだったので、簡単なヒントを出すと
・しりとりとは先頭文字と末尾文字が必ず紐付いている。
・先頭文字や末尾文字が同じものが複数ある。
・もしかしたら逆引き(しりとりが終わる単語から遡る)のが楽かも?
後から気づいたので、私は試してません。
こんなものでしょうか。
基本的な処理の流れとしては
1、各単語に後続しうる単語の番号を配列に記録
2、先頭の単語の番号を前から順に一時配列にいれ
そこから後続しうる単語の番号をまた順にいれ
最大長であれば戻り値候補として記憶
後続しうる単語がなくなったら一時配列の末尾を除き
一つ前の単語の後続候補を次に進める
これを先頭の単語が84個全部巡るまで続ける
3、戻り値の単語番号を単語に戻す
というような流れです
基本的にはしりとりが成立しうる組み合わせしか
試行しないので答えが短ければいくんですけどね…
No.5
- 回答日時:
とりあえず、ソースは読んでいないのだけど・・・
84種類を 一個づつ 減らしながらかけていったらー
3.3142401345654E+126
うん。天文学的数字になりました。
まぁ、ヒントも出ちゃってるし、当たり前過ぎるだし、この程度なら言っても差し支えないかなと思うので言うと、最初の一文字で分類するのがいいんじゃない?
No.2
- 回答日時:
こういうのは、総当たりでやってたら、物凄い勢いで処理回数が増えていきます。
「組み合わせ爆発」と言われています。
確かに、遅いマシンでは遅いですが、このような問題では、多少マシンを速くしたところで焼け石に水です。
なので、アルゴリズムを工夫して、無駄をいかに省くか、というのがコツになります。
なんとか無駄な選択肢を減らせないか、を考えましょう。
ところで、そのサイトに
> 解答送信の有無を問わず、模範解答のネタばれにつながるような各種行為、別人による不正解答は、固くお断り申し上げます。
とあるのですが、大丈夫でしょうか?
多分、模範解答には全くならないので大丈夫です(笑)
回答としても、コード自体は間違っていないか
無限ループを起こすようなことにはなっていないか
この程度ならマシンスペックとかPHPの設定とかでどうにかなるレベルか
それともこのやり方ではスパコンつかってもムリなレベルなのか
その辺の回答をいただきたいと思っています
無駄な選択肢を減らす工夫、考えてみます
ありがとうございます
No.1
- 回答日時:
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が見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- JavaScript EasyUIのSubGrid(jquery)におけるObjectに入れた連想配列について 1 2022/05/02 11:21
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- その他(プログラミング・Web制作) ColabでのPytorchのエラー 1 2022/11/19 20:51
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- C言語・C++・C# プログラミングの授業の課題です 1 2023/01/17 22:15
- その他(プログラミング・Web制作) pandasでまとめてインデックスを削除するにはどうすればいいですか? たとえば、以下のプログラムで 1 2022/07/31 23:09
- Visual Basic(VBA) vb.netです。2次元配列の要素をFor Eachでひとつづつ取得したい。 4 2022/07/05 11:30
- PHP PHPで画像の渡しが上手く行きません。 1 2023/02/02 09:39
- Excel(エクセル) 2つのVBAを一緒にしたら機能しなくなりました(エクセル) 7 2022/06/02 12:41
- Visual Basic(VBA) 前回ご教授いただいたコードに覚えたてのループ処理で品名りんごAから順に20回for nextでループ 7 2023/01/13 22:01
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
プルダウンメニューにDBの内容...
-
日付から順にデータを並び替えたい
-
順位を付ける時のスコアの重複...
-
外部のテキストファイルを読み...
-
pg_insertで現在の時刻を挿入す...
-
if の中の 複数のor についてお...
-
PHPのプルダウン式のジャンプ設...
-
重複確認
-
別ファイルの構造体の値を読み...
-
総当り表
-
PHPで変数名にハイフンを使うに...
-
foreachで上限回数指定方法また...
-
配列をループでたくさん宣言し...
-
[PHP] fputcsv()関数でファイル...
-
クロス集計で商品名かつサイズ...
-
PostgreSQLの配列項目のデータ...
-
Smartyでtplファイルから配列を...
-
【PHP】配列のキー名の修正は可...
-
am()の使い方
-
C言語の配列をPush(追加)する...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
プルダウンメニューにDBの内容...
-
phpとmysqlで「あいまい検索」...
-
PHP5の外部コマンド実行で、バ...
-
「ローマ字 -> ひらがな」へPHP...
-
Mysqlとphpでソートや更新時の...
-
PEAR・MDB2のモジュールロード...
-
HTTPのメッセージボディについ...
-
数学の「組み合わせ」を求める...
-
順位を付ける時のスコアの重複...
-
Zend_Form_Element_Hash
-
占いのPHPを作成中ですが・・・
-
しりとり 無限ループ?
-
日付から順にデータを並び替えたい
-
多次元配列のカウント+1の仕方
-
要素(文字列)から指定値を検索
-
flickrでの画像を取得について
-
mysqlにinsertするとエラーがで...
-
選択日と終了日を配列で取得したい
-
$xml要素を階層指定して取得し...
-
月一覧を取得するには?(20120...
おすすめ情報