- ベストアンサー
アルゴリズムについて
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
合っています。
関連するQ&A
- アルゴリズム
アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。 ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。 (1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。 解) n=100*2 =200 (2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。 解) 求める問題の大きさをxとおくと n=(100^2)*100 =10000*100 =1000000 (3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。 解) 2^40=(2^20)*(2^20) =1*(2^20) =2^20[時間]
- ベストアンサー
- その他（プログラミング・開発）
- 順列生成アルゴリズムについて仕組みを教えてください
ある本を参考に順列を出力するプログラムをJavaScript用に書き直しました。 上手く動いたのですが、どうして、順列を出力できるのか理解できません。 まず、プログラムは以下になります。 <script> // 対象の配列 var array = [0,1,2,3]; // 配列の数 var N = array.length; // 順列を出力するプ関数 function permutation( n ) { // テンポラリー用 var temp; // 順列を生成する処理部分 if ( n < N ) { for ( var i = n; i < N; i++ ) { // （1）対象の配列から数字を一つ取り出して、他の数字と入れかえる temp = array[n]; array[n] = array[i]; array[i] = temp; // （2）再起呼び出し permutation( n + 1 ); // （3）入れ替えた数字を元に戻す temp = array[n]; array[n] = array[i]; array[i] = temp; } } else { // 出力 console.log( "結果：" + array); } } // エントリーポイント permutation(0); </script> 処理を理解するために、コメントの（1）や（3）などに console.log を入れて、出力したところ、全く理解できないスタックの流れになっていました。 具体的には、1～2を条件を満たす間繰り返した後、一度出力（スタック開放）します。その後、（3）の処理をするのですが、その直ぐ後に、また（3）の処理をするのです。 具体的なログは以下のようになりました。 【n=0】**************************// 関数の呼出しと呼出し時の引数です。 i=0 再帰前:1回:0,1,2,3 n=0 // （1）の処理です。0,1,2,3は、対象の配列です。 【n=1】************************** i=1 再帰前:2回:0,1,2,3 n=1 【n=2】************************** i=2 再帰前:3回:0,1,2,3 n=2 【n=3】************************** i=3 再帰前:4回:0,1,2,3 n=3 【n=4】************************** スタック開放：0,1,2,3 n=4 再帰後:1回:0,1,2,3 n=3 // （3）の処理です。 再帰後:2回:0,1,2,3 n=2 // なぜ連続して呼ばれているのか i=3 再帰前:5回:0,1,3,2 n=2 【n=3】************************** i=3 再帰前:6回:0,1,3,2 n=3 【n=4】************************** スタック開放：0,1,3,2 n=4 再帰後:3回:0,1,3,2 n=3 再帰後:4回:0,1,2,3 n=2 // なぜ連続して呼ばれているのか 再帰後:5回:0,1,2,3 n=1 // なぜ連続して呼ばれているのか i=2 再帰前:7回:0,2,1,3 n=1 【n=2】************************** “なぜ連続して呼ばれているのか”の部分が理解できません。予想では、再帰後の部分が一度呼ばれて、このプログラムは止まってしまうと思うですが、最後まで動きます。 なぜ、止まらずに動くのか教えてください。
- ベストアンサー
- JavaScript
- アルゴリズムのフローチャート（ヒストグラム）
０以上１０以下の整数を入力として繰り返し受けつけ、階級の幅が３であるようなヒストグラムを出力する。 終了記号は－１とする。 始 ↓ ｉ←０ ↑→→↓ ↑ Ｘ[ｉ]←０ ↑ ↓ ↑←←ｉ≧４ ＮＯ ↓ ↓ＹＥＳ ↓ 入力：Ｎ ↓ ↑→→↓ＹＥＳ ↑ ↓ ↑ Ｎ＝－１ →ＹＥＳ→出力：Ｘ→終 ↑ ↓ ↑ ↓ＮＯ ↑ ↓ ↑ Ｎ←Ｎ/３ ↑ ↓ ↑ Ｘ[Ｎ]←Ｘ[Ｎ]＋１ ↑ ↓ ↑←←↓ 見にくい図で申し訳ありません。 このようなフローチャートがあるのですが、全体の流れの意味がよくわかりません。 特に後半の「Ｎ←Ｎ/３」以降はどういった意味なのでしょうか？ よろしければ解説をお願い致します。
- ベストアンサー
- その他([技術者向] コンピューター)
- 転置行列アルゴリズム
こんにちは。プログラミングを学んでいる学生です。 N*Nのint型の配列を転置するCプログラムでなるべく性能の良いものを書け、という課題が出て、それと同時にシンプルな(性能が悪いと思われる)サンプルが配布されてました。 ですが、それを超えるようなアルゴリズムがどうしても思いつきません。 何かアドバイスいただけたらうれしいです。 配布メソッド: #define N 64 //Nは64,128,512,...,2048をはかる typedef int matrix_t[N][N]; void naive_rotate(matrix_t src, matrix_t dst){ int i,j; for(i=0;i<N;i++) for(j=0;j<N;j++) dst[N-1-j][i]=src[i][j]; return; } メソッドの７行目をdst[j][i]にしたらあまり変化ありませんでした。 また、i==Jのときcontinueするようにしたら、逆に遅くなってしまいました。
- ベストアンサー
- C・C++・C#
- 数学の確率の問題です。
数学の確率の問題です。 下の問題(2)の問題なのですが、解答は いっぺんの長さがi(i=1,2,3,.....n)の正方形の総数は(n+1-i)個............ と書いてあるのですが、どうして正方形の個数が(n+1-i)になるのでしょうか？
- ベストアンサー
- 数学・算数
- 数独を解くアルゴリズム
バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。 コンパイルエラーはありません。 表示の関数は省いてあります。 よろしくお願いします。 #include <stdio.h> #define M 3 //小さいブロックのサイズ #define N M*M //全体のサイズ #define MTX N*N //全体のマス数 int sudoku[N][N]={ {0,2,4,5,0,0,6,0,0}, {0,0,6,3,2,0,0,0,4}, {0,0,5,0,9,0,0,8,3}, {0,0,8,4,0,3,0,0,1}, {0,6,1,9,0,0,4,3,0}, {7,0,0,1,0,0,5,0,0}, {8,3,0,0,4,0,9,0,0}, {4,0,0,0,3,5,8,0,0}, {0,0,7,0,0,9,3,4,0} }; /* 候補がOKかどうかチェック */ int OKkouho(int x, int y, int k) { int i,j; int p,q; for(i=0; i < N; i++){ //その行に候補は入るか if(sudoku[y][i] == k) return 0; } for(j=0; j < N; j++){ //その列に候補は入るか if(sudoku[j][x] == k) return 0; } p = x/M*M; q = y/M*M; //そのブロックに候補は入るか for(j = q; j < q+M; j++){ for(i = p; i < p+M; i++){ if(sudoku[j][i] == k) return 0; } } return 1; } void Solve(int level) { int k; int x,y; if(level >= MTX){ printf("OK"); return; } x = level%N; y = level/N; if(sudoku[y][x]) Solve(level+1); else{ for(k = 1; k <= N; k++){ if(OKkouho(x,y,k)){ sudoku[y][x] = k; Solve(level+1); sudoku[y][x] = 0; } } } } int main(void) { Solve(0); return 0; }
- 締切済み
- C・C++・C#
- 場合の数の問題です。
数直線上の整数点 x＝1,2,3,・・,n に、合計ｎ個の黒又は、白の石を１つずつ、黒石どうしは隣り合わないように置く。黒石を３個使う置き方は何通りあるのか。ただしｎ≧5 とする。 一見すると、とても簡単な問題ですが、自分が出した答えと解答が間違っていたので、あれ？と思い、疑問に思い、質問することにしました。 自分の解答は・・・ （i）白石が、x＝１、ｘ＝ｎにあり、その他は２～ｎ－１にある場合 黒石は、白石の間のｎ－４の中に、３個置くため、 n-4C3通り （ii）白石がｘ＝１ その他は２～ｎー１にある場合 黒石は、ｎ－３の中に、３個置くため、 n-3C3通り （iii） 白石がｘ＝ｎ、その他は、１～ｎ－１にある場合も、（ii）と同様で あるため、n-3C3通り （iv）白石がｘ＝２～ｎ－１にある場合 黒石は、両端か、白石の間のｎ－２個の中から、３個選ぶから、 n-2C3通り （i）～（iv）より 求める場合の数は、(n-4)(n-5)(4n-21)/6 となったんですが、答えとは違っていました。おそらく、９９％は自分の解答が間違っているとは思うのですが、どなたかなぜ僕の解答が間違っているのかご教授ください。宜しくお願いします。
- ベストアンサー
- 数学・算数
- アルゴリズムの名前を教えてください
16ビットのデータが、たとえば1000個、配列で与えられているとします。 unsigned short data[1000]; このデータをしらべて、重複するものを除いて何種類の値があるかを数える場合、一番素朴な方法だと、次のようにやると思います。 int i, j; int count = 0; for(i = 0; i < 1000; i++) { for(j = 0; j < i; j++) { if(data[j] == data[i]) { break; } } if(i == j) { count++; } } この方法だと、２重のループがあって処理に時間がかかります。そこで、メモリに余裕があれば内側のループをやめて、 int i; int count = 0; int flag[0x10000]; int n; for(i = 0; i < 0x10000; i++) { flag[i] = 0; } count = 0; for(i = 0; i < 1000; i++) { n = data[i]; if(flag[n] == 0) { flag[n] = 1; count++; } } これだと、２重のループを使うものよりは速くなりますが、データが1000個しかないのに、65536個のflagをクリアするのに時間がかかり、今ひとつです。 ところが、次のような賢い方法があり、２重のループも配列のクリアも無くすことができます。 int i; int count = 0; unsigned short flag[0x10000]; unsigned short link[0x10000]; int n; for(i = 0; i < 1000; i++) { n = data[i]; if(flag[n] >= count || link[flag[n]] != n) { flag[n] = count; link[count] = n; count++; } } 私がこのアルゴリズムを知ったのはかなり昔なので、どこで知ったのか思い出せないのですが、これほど賢いアルゴリズムだから何か名前がついていると思うのですが、それがわかりません。 名前がわからないので、人に頼んだりする時、上のような長い説明をしなくてはなりませんが、名前がわかっていれば「？？法でやっといて」、と言えばいいのですけど。
- 締切済み
- C・C++・C#
- アルゴリズムに関する問題
こんばんわ、いくつかの問題につまってしまったので解答と簡単な解説をお願いします； 【問1】 4桁の数字( a1a2a3a4 )をハッシュ法を用いて配列に格納したい。 ハッシュ関数をmod（ a1 +a2 +a3 +a4 ,5 ）とし、求めたハッシュ関数値に対応する位置の配列要素に格納する場合、９５７６は（ア）～（オ）のどこに入るか。 ここでmod（x，5）の値は、xを5で割った余りとする。 位置 配列 ０ （ア） １ （イ） ２ （ウ） ３ （エ） ４ （オ） 【問２】 相違なるｎ個のデータが昇順に整列された表がある。この表を１ブロックｍ個に分割し、各ブロックの最後尾のデータだけ線形検索することによって、目的のデータを探し出す。 次に当該ブロック内を線形検索して目的のデータを探し出す。 このときの平均探索（比較）回数は（ア）～（エ）のうちどれか。 ここでｍ＜ｎとし、目的のデータは必ず表の中に存在するものとする。 （ア） （イ） （ウ） （エ） ｎ ｎ ｎ ｍ ｎ ─ ─ ｍ ＋ ─ ─＋─ ｍ ２ｍ ｍ ２ ２ｍ 【問3】 次の手順はシェルソートによる整列を示している。 データ列”7，2，8，3，1，9，4，5，6”を手順（１）～（４）に従って整列すると手順（３）を何回繰り返して完了するか。 ここで、〔〕は小数点以下を切り捨てる。 ＜手順＞ （1）〔データ数÷3〕→Ｈとする。 （2）データ列を互いにＨ要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を挿入方を用いて整列する。 （3）〔Ｈ÷3〕→Ｈとする （4）Ｈが0であればデータ列の整列は完了し、0でなければ（2）に戻る。 以上になります。
- ベストアンサー
- その他([技術者向] コンピューター)
