- 締切済み
データ構造とアルゴリズムの問題です
要素数がnである配列aの要素の最大値を求めるアルゴリズムのループ端によるフローチャートを完成せよ(前判定繰返し) max =a[0] i=1; while i<n do{ if(a[i]>max)max=a[i]; i++; } a[0] → max 1 → i 前判定繰返し □ | yes a[i]□max-----| | □ NO i+1 → i 前判定繰返し □の中を埋めるんですが教えてください
- dreamcloudxxx
- お礼率5% (4/76)
- C・C++・C#
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- ok-kaneto
- ベストアンサー率39% (1798/4531)
何を教わりたいの？
関連するQ&A
- データ構造とアルゴリズムの問題です
要素数がnである配列aの要素の合計を求めるアルゴリズムのループ端によるフローチャートを完成せよ(後判定繰返し) sum =a[0] i=1; do{sum=sum+a[i]; i++; }while i<n; a[0] → sum 1 → i 後判定繰返し | □→sum; i+1 → i | □ 後判定繰返し □の中を埋めるんですが教えてください
- ベストアンサー
- C・C++・C#
- フローチャートの書き方
要素数がnである配列aの要素の最大値を求めるアルゴリズムのループ端によるフローチャートを完成せよ(前判定繰返し) max =a[0] i=1; while i<n do{ if(a[i]>max)max=a[i]; i++; } フローチャートでかくとどうなりますか？
- 締切済み
- C・C++・C#
- アルゴリズムの問題です
以下のフローチャートは、基本選択法でデータを昇順（小→大）にソートしたものなのですが、整数の一次元配列に格納されているデータ（１００個）を降順（大→小）にソートするフローチャートを作成するには、どこの部分を変化させればいいのか教えていただけませんか？ 手書きなので見にくいですがよろしくお願いします。 開始 ｌ 整数配列A(100)と整数変数I,J,N,P,MIN,TEMPを宣言 ｌ データの個数N の値を読む ｌ ループ１の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を読む ｌ ループ１の終了 ｌ ループ２の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を出力 ｌ ループ２の終了 ｌ ループ３の開始 I = 1,2,3, ・・・,N-1 ｌ MIN = A(I) ｌ P = I ｌ ループ４の開始 J = I+1,I+2,I+3, ・・・,N ｌ ｌ yes A(J) < MIN ーーーーーー MIN = A(J) ｌ no ｌ ｌ P = J ｌ ｌ ｌ←ーーーーーーーーーーー ｌ ループ４の終了 ｌ TEMP = A(I) ｌ A(I) = A(P) ｌ A(P) = TEMP ｌ ループ３の終了 ｌ ループ５の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を出力 ｌ ループ５の終了 ｌ 終了
- ベストアンサー
- その他([技術者向] コンピューター)
- 走査アルゴリズムについて
ｎ個の要素の配列ｘ[]について 配列ｘの連続した要素（部分配列）でその和が最大になるものを見つけて、 その和を出力するアルゴリズムについてです。 これなのですが解き方の考え方に 「x[0...n]までの部分配列の最大和は、x[0...n-1]の部分配列の最大和か、x[n]から左方向に伸びた配列の和のいずれかである。」 とあり プログラムには float maxSoFar(float x[], int length){ float maxsofar = 0; float maxendinghere = 0; for(int i = 0; i < length; i++){ maxendinghere = max(0.0f, maxendinghere + x[i]); maxsofar = max(maxsofar, maxendinghere); } return maxsofar; } とあるのですが、アルゴリズムの仕組みがよくわかりません。 なぜ上のような説明でこのようにプログラムできるのかが わからないので、どなたかうまい説明できる人お願いします＞＜
- ベストアンサー
- 数学・算数
- アルゴリズムの正当性について
線形探索法のアルゴリズムの擬似コードを書いて、そのアルゴリズムの正当性をループ不変式を用いて証明するという課題があります。 擬似コードは以下のような流れにしようと思いますが、この場合成り立つループ不変はどのようなことになりますか？ 配列A[a1..an]に対してv=A[i]ならば添字iを、vがAの中になければNILを出力するアルゴリズムです。 for i ←1 to N if A[i] = v return i return NIL
- ベストアンサー
- 数学・算数
- アルゴリズムによる整列方法について
以下の問題を授業外課題として出されましたがわかりません。身近に分かる人物もいません。 先生も答えてくれません。 解答お待ちしております。 １．以下の文章の空欄を埋めよ．但し，((14)),((15)) については，選択肢から最も適切なものを選び，記号で答えよ．加えて，解答の過程を詳しく述べよ。 高速な整列として以下のアルゴリズムによる方法を考える．以下では，整数データを昇順に配列するも のとする． 前段階として，データを半々に二つのグループ I と II に分割し，それぞれを独立に整列する． while (両グループに要素が残っている) do if (グループ I の最小要素 < グループ II の最小要素) then グループ I の最小要素を出力場所に移し，グループ I からは削除する else グループ II の最小要素を出力場所に移し，グループ II からは削除する endif done while (グループ I に要素が残っている) do グループ I の要素を出力場所に移し，グループ I からは削除する done while (グループ II に要素が残っている) do グループ II の要素を出力場所に移し，グループ II からは削除する done この整列に要する計算量 T(n) を求める．但し，n は整列するデータの量である．前段階の整列では，半分のデータ量の整列を 2 回行うので ((1)) だけの計算を要する．次に，3 個の while 反復のいずれについても， 「反復を 1 回行うごとに要素が一つだけ出力場所に移動する」 ことから，3 個を合計すると反復の中身は正確に ((2)) 回実行されることが分かる．1 回の実行に a だけの時間がかかるものとすれば，全体で ((3)) となる．従って次の関係式が成り立つ． T(n) = ((4)) 簡単のため，n = 2^p であるとすると， T(n) = ((5))×T(2^((6)) ) + ((7)) = ((8)) × T(2^((9)) ) + 2 × ((7)) ・ ・ ・ = ((10)) × T(2^0) + ((11)) T(2^0) = ((12)) なので，T(n) を a と n のみを用いて表すと， T(n) = ((13)) であり，これは， ((14)) に比例し，計算量のオーダーは ((15)) といえる． ((14)),((15)) の選択肢 a. n b. n^2 c. 2^n d. n log n e. log n f. いわゆる「指数オーダー」であり，アルゴリズムとして全く実用に耐えない g. いわゆる「バカソート」と同じであり，n がごく小さい場合を除いて実用には適さない h. 経験上最速とされるソート法には及ばないが，それほど大きくない n に対しては実用に耐える i. 経験上最速とされるソート法と同じであり，十分大きい n に対しても実用に耐える
- 締切済み
- 数学・算数
- 隣接交換法のアルゴリズムについて
隣接交換法(バブルソート)のアルゴリズムについて悩んでいます。 Q:配列「データ」には10個の要素があり、この配列「データ」を降順に並び替えるための隣接交換法アルゴリズムは？ 一応、自分なりにアルゴリズムを考えたのですが、ループを抜けるチャンスが、【『要素』の数-1】回あるといわれ、それを考慮したアルゴリズムを考えよ、と言われました。 (そのチャンスというのが、どこにくるのかがわかりません。) http://oshiete1.goo.ne.jp/kotaeru.php3?q=290051も参照しましたが、よくわかりません。 すみませんが、教えていただけないでしょうか？よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- ヒープソートの問題について
分からない問題があります。 どなたかお教え下さい。よろしくお願いします。 Max-Heapify (A,i) 1. L <- 2i 2. R <- 2i+1 3. if L<= heap-size[A] かつ A[L] > A[i] 4. then largest <- L 5. else largest <- i 6. if R<= heap-size[A] かつA[R] > A[largest]) 7. then largest <-R 8. if largest !=i 9. then 値の交換A[i] <-> A[largest] 10. Max-Heapify (A,largest) Build-Max-Heap (A) 1. heap-size[A] <- length[A] 2. for i<- ⌊length[A] /2⌋ downto 1 3 do Max-Heapify (A,i) Heap-Sort (A) 1. Build-Max-Heap (A) 2. for i<- length[A] downto 2 3 do 値の交換 A[1]<->A[i] 4 heap-size[A] = heap-size [A] – 1 5 Build-Max-Heap (A) 上に示す疑似コードを参考に、以下の問いに答えなさい。ただし、length[A]、heap-size[A]は配列Aの要素数、配列Aに格納されているヒープの要素をそれぞれ示す。 a. ヒープに格納される要素数をnとし、要素の添字の範囲を求めなさい。 b. 配列A=<3,9,8,15,4,2,5,1,7,10>からBuild-Max-Heapによりmax-ヒープを生成したときの結果を示しなさい。 c. 上のHeapsortは、配列を正しくソートするか？しないなら、正しくソートするようにするにはどのように修正すればよいか？理由と共に答えなさい。 d. マージソートと比較してヒープソートの良い点を述べなさい。
- 締切済み
- 科学
- アルゴリズムの名前を教えてください
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#
- このフローチャートがわかりません＞＜
あらかじめ値が格納されている配列ｔ（要素数：10個）から、最大値を求めるフローチャートと最小値を求めるフローチャートをそれぞれ作成した。空欄を埋めなさい。 横書きですいません＞＜ 開始-□-□-ループ□-◇-ｃｎｔ+１→１-ループ-min出力-終了 というフローチャートです。 □◇が空欄で◇は判断記号です。 フローチャートをまっすぐ進むとイエス、曲がるとノーとなります。 解説できる方いましたらよろしくお願いします。
- 締切済み
- 数学・算数
