- 締切済み
アルゴリズム
クイックソートは最初から配列変数が降順に並んでいる場合に遅くなる。この解決策を考えて説明せよ。また、うまくいく理由を述べよ。 要素数nの配列変数を整列する場合 主語と述語があって、マル(。)で終わる文を複数書くこと。 キーワードの羅列、体言止めはＮＧ 「解決策」と「うまくいく理由」を説明する。 よろしくおねがいします。
- naruto54
- お礼率25% (1/4)
- その他（学問・教育）
- 回答数3
- ありがとう数0
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- utun01
- ベストアンサー率40% (110/270)
これは問題文そのままなんですかね。 > 主語と述語があって、マル(。)で終わる文を複数書くこと。 > キーワードの羅列、体言止めはＮＧ 対象はどこの小学生かって感じですが・・・； この問題のみを解決する方法は実に単純ですよ。 クイックソート用の再帰ルーチンに入る前に、配列が降順になっているかどうか判断を入れればいいだけでしょう。 たぶんこの問題の意図とは違う回答な気がしますが、業務的な開発上はこれが最も低コストで効果的な方策かと思います。
- chie65535
- ベストアンサー率43% (8525/19380)
ここの回答は「コピペルナー」の監視対象になっているから、ここで得た回答を丸写しすると、コピペルナーで引っ掛かって、課題の再提出を食らいますよ。 コピペルナーについて http://www.ank.co.jp/works/products/copypelna/
- Tacosan
- ベストアンサー率23% (3656/15482)
であなたの質問は?
関連するQ&A
- 文の主語と述語について
「きれいな女性が美しい心を持っているとは限らない。」 という文の主語と述語は何か、どなたかおわかりの方がいらっしゃればお教えください。 「主語」も「述語」も、文節についての呼び方です。 ですから、とりあえず私は、上の文を、文節にわけた上で、「いるとは」という文節を主語、「限らない」という文節を述語と考えました。 ですが、単語を品詞で分類した際、助詞とくっついて主語になるのは体言です。 「いるとは」は、動詞「いる」と、助詞「と」と「は」に分けられますが、体言はありません。 それでは、「いるとは」は主語ではないことになるのでしょうか？ だとすれば他に何が主語になるのでしょうか？ 仮に「いるとは」ではなく、「女性が」が主語であると考えると、「女性が―限らない」とつながるのはおかしいので、やはり「女性が」が主語であるとは考えられません。 よい説明をお待ちしております。
- 締切済み
- 日本語・現代文・国語
- 述語「名詞＋だ」にかかる修飾語は、連体修飾語？
初歩的な質問でお恥ずかしい限りですが、よろしくお願いいたします。 中１国語の教科書（光村）に、文法の修飾語に関する説明の例題として、以下のものがありました。 『色あせた写真は祖母の宝物だ。』 これを文の成分で示すと、 色あせた／写真は／祖母の／宝物だ。 ⇒修飾語／主語／修飾語／述語 …というふうになり、「色あせた」は「写真は」を、「祖母の」は「宝物だ」を修飾する、ということまでは分かります。 では、「祖母の」は、連体修飾語と連用修飾語のどちらですか？ 同じく、教科書の説明には、 『体言…主語となる文節の中で、中心となる単語。 用言…それだけで述語となる単語。』 『連用修飾語…用言を含む文節を修飾。』 連体修飾語…体言を含む文節を修飾。』 と書かれいます。 述語「宝物だ」は「名詞＋だ（助動詞）」であって、単独で述語となることができる単語はないですよね。（この時点ですでにあまり自信がないのですが…） ですから「祖母の」は「宝物」という名詞にかかる、連体修飾語だと思うのですが、上記の体言の説明では、体言は主語の文節の中にある単語であると限定されてしまっています。 いったい「祖母の」は連体修飾語と連用修飾語のどちらなのでしょうか…？ 私が学生のころは、「体言は名詞」「用言は動詞・形容詞・形容動詞」という理解で、体言は主語限定というような教わり方はしなかったように思います。 私が覚えていないだけかもしれませんが…。 どなたか、解説をお願いいたします。
- 締切済み
- 日本語・現代文・国語
- 二次元配列のソート PHP
タイトルのとおりソートを行ってくれる関数を探しております。 $buf[][]の二次元配列の変数を日付の降順に並べ替えたいのですが、そういった関数は用意されていますか？ sort()、rsort()では不可能かと思います。 以下、二次元配列の値です。配列三番目の日付の降順で再格納したいです。 ( [0] => Array ( [0] => 1[1] => name1 [2] => 2006-08-18 ) [1] => Array ( [0] => 2 [1] => name2[2] => 2006-08-28 ) [2] => Array ( [0] => 3[1] => name3 [2] => 2006-08-18 ) [3] => Array ( [0] => 4 [1] => name4[2] => 2006-08-18 ) よろしくお願いいたします。
- ベストアンサー
- PHP
- 乱数の順位付けのアルゴリズム
[0,1]の範囲で乱数を1000個、配列に発生させて、小さいもの100個を選び出すアルゴリズムということを考えます（知りたいのは数値と配列番号、むしろ配列番号が大事）。まず想定できるのはソートですが、それにもいろんなものがあり、クイックソート、バブルソートなどが挙げられます。ソートのアルゴリズムは既に開発されつくしたのかもしれませんが、どのようになっているでしょうか。一番高速な（かつ間違いない）な方法が１つあればそれを採用したいのですが。 そして１つ厄介なのですが、そのトップ100個以外の900個はソートする必要がないということです。私が考えているアルゴリズムは、 １．既に100個の選ばれていると仮定（初期はすべて１） ２．新しい1個が来たとき、100個の最低値よりも小さいなら考慮の対象なのだから最低値を交換してその100個でソートする。そうでない場合は何もしない。 ３．次の新しい1個を調べて、項目２をする。 ４．発生させた1000個でそれを繰り返す。 このアルゴリズムだと100個のソートを何百回かぐらいやることになります。 これをするぐらいだったら1000個のソートを1回やればいいということになるでしょうか（不必要な残りの900個もソートされてしまう）。あるいはその1回の1000個のソートの中でやる必要のない処理を排除する工夫があるかもしれません。 問題が難しくなく、素人っぽくコード化できると思いますが、その分、非効率なところも放置されそうなので高速化できるコードの書き方があったら教えて頂きたいのですが。コードというよりアイディアだけ説明していただいても助かります。実際はフォートランになると思いますが。よろしくお願いします。
- 締切済み
- C・C++・C#
- V.B.に特化した文字列の整列方法と整列方法の自動選択
小さくはない配列の整列で 通常法（本来の名称忘却） http://oshiete1.goo.ne.jp/kotaeru.php3?q=209365内回答 No3 for k=j to i を For k=j+1 to iに変更 クイックソート http://www.ne.jp/asahi/protech/hiroaki/programing/vb.html シェルソート http://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/SSort.htm ループ変数を倍精度整数型に，配列を文字配列に，変数名を自分の使っている命名法に 再帰参照回数を減らすように，末尾も含めて整列されるように変更 文字列を SortDt$(N&)=Str$(Rnd(1)) で指定し 富士通 FMV Diskpower S3 20 (Win 95+VB6.0(V.S), 購入直後の状態)で実行した結果， 約30秒間(V.B. Timer関数で測定)で，クイックソート，シェルソート，通常法で実行可能回数が Visual Basic 6.0 SP3 コンパイラ n&=3 208943, 209490, 248245 n&=10 114149, 138935, 215415 n&=30 47967, 39833, 163284 n&=100 14118, 8353, 83524 n&=300 3913, 2064, 30516 n&=1000 987, 414, 9750 n&=3000 281, 105, 3348 n&=10000 68, 21, 947 となり，大型コンピューター(Fotran)で過去に経験しているクイックソート，シェルソートの利点を得られませんでした。 又，上記表はn&が対数目盛でほぼ等間隔になるように選択しました。n&に対する整列時間の変化が過去に報告されている内容とは異なります。したがって，整列に関する過去の経験は使えません。 大型コンピューターでは，クイックソートよりも早い整列方法が発表される等の研究が進んでいます。 おそらく Visual Basic 6.0 用に特化した整列方法があるかと思いますが，ご存知の方いらっしゃいませんか。 整列方法の自動選択(Win95で表示ルーチンの自動選択をマイクロソフトで行なっていましたから)を考えています。 関係情報をご存知の方いらっしゃいませんか。
- 締切済み
- Visual Basic
- Ｃ言語 クイックソートについて
以下の数字を用いて・・・・ num[10] = {21, 46, 87, 9, 32, 33, 57, 87, 12, 43} クイックソートで整列する時，データの入れ替え状況，配列の内容の変化について，データの入れ替え過程をプログラムでない形で説明をお願いします。アルゴリズムの特徴がわかる説明と入れ替え過程を示してほしいです。 以下の数字を用いてお願いします。 例: ●●で分割: { } ●●で分割: { } ・ ・ ・ ・ 整列後: { }
- 締切済み
- C・C++・C#
- 何度もすいません。クイックソートのプログラムを教えてください。
課題の丸投げです。本当にすいません。 学校の課題で、整数配列をクイックソートにより降順に並べる関数を実装したプログラムを作る。という課題で int qsort(int date[], int size)という関数が与えられていて、sizeは配列の大きさを示す。またソートが成功した場合は１を、失敗した場合は０を返値とする。ということなんですがsizeを使ってクイックソートをどうやったら良いのか分からないので教えてください。 課題の丸投げですが、すぐ返事ほしいです。 よろしくお願いします。
- 締切済み
- C・C++・C#
- クイックソートについて
下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }
- 締切済み
- C・C++・C#
- クイックソートのプログラム
『n個のデータを配列a[0],a[1],...,a[n-1]に読み込んでおき、クイックソートで降順に並べ替えるプログラムを作る。』 という問題が出ているのですが、Ｃ言語初心者の私には全くわからなくて困ってます。 このプログラムを教えてください！お願いします！
- ベストアンサー
- C・C++・C#
