問題タブ [divide-and-conquer]

2^k * 2^k サイズのボードが与えられましたが、タイルの 1 つがランダムに削除され、欠陥のあるボードになっています。タスクは、3 つのタイルで作られた L 字型の図形である「トロミノ」で埋めることです。

それを解決するプロセスはそれほど難しくありません。ボードが 2x2 の場合、1 つのトロミノだけでボードを埋めることができます。それ以上のサイズの場合は、4 つに分割し (4 つの 2^(k-1) サイズのボードを作成)、中心点に 1 つのトロミノを配置して、各象限に 1 つの塗りつぶされたタイルを配置する必要があります。その後、すべてのタイルがランダムな色のトロミノで満たされるまで、ボードを再帰的に埋めることができます。

私の主な問題は、実際にコードを実装することです。私の Java プログラミングのスキルは概してかなり弱く、単純にどこから始めればよいかを見つけるのに苦労することがよくあります。実行する唯一の作業は、tiling クラスの tile メソッドです。このメソッドは、入力としてタイルへの不足ボード、タイルを開始する行と列、および塗りつぶすタイルの数を受け取ります。これは宿題の問題なので、手引きや開始点を探しているだけです。どんな助けでも大歓迎です。

}

}

}

学校のプログラミング チームのオンライン ジャッジ用に Pascal プログラムを作成しようとしています。プログラムは a^b mod c を出力する必要があります。ここで、a、b、c は入力として与えられます。テストケースはすべて非常に大きな数であるため、ブルートフォースを使用することはできません。

いくつかの調査の結果、分割統治戦略を使用できることがわかりました。これは私が思いついたコードです：

しかし、オンライン審査員は不正解を返しました。コードの問題点を指摘できる人はいますか?

Coreman の MergeSort アルゴリズムを Java で実装しようとしています。しかし、それは常に私に間違った出力を与えます。

ソート前：[86, 8, 60, 9, 49, 73, 37, 59, 98, 69]

ソート後 : [8, 8, 9, 37, 37, 49, 49, 59, 69, 69]

以下は私のコードです：

値を出力してコードをデバッグしようとしましたが、ここで何が問題なのかを見つけることができません。ここで何が間違っている可能性があるかを提案してください。

この演習の2番目の問題bおよびdのサブ問題を解決しようとしました：http：//courses.engr.illinois.edu/cs473/sp2010/homework/hw1.pdf

私はbを次のように解決しました：

私の最初の質問はそれです：私の解決策は問題2 / bに対して正しいですか？私の2番目の質問は、問題2 /dで何をすべきかということです。これは私にとって少し奇妙です。

お手数をおかけしますが、よろしくお願いいたします。

まず、私が解決しようとしている問題を説明させてください。非常に複雑な財務予測を行うサードパーティのライブラリとコードを統合しています。この質問の目的のために、x を渡すと y を返すブラックボックスがあるとしましょう。今、私がする必要があるのは、特定の出力 (y) に対する入力 (x) を見つけることです。可能な限り低い入力値と最も高い入力値を知っているので、次のアルゴリズムを書きました。

1. 開始入力範囲の定義 (最小入力値から最大入力値)
2. 範囲を 2 つの等しい部分に分割し、中間値の出力を見つけます
3. どの半分の出力が当てはまるかを見つけます
4. 範囲が小さすぎてそれ以上分割できないまで、手順 2 と 3 を繰り返します。

このアルゴリズムはうまく機能します。問題はありません。しかし、この問題を解決するためのより速い方法はありますか?

マージソートやクイックソートなどのアルゴリズムが分割統治パラダイムを使用していることは知っていますが、時間の複雑さを下げるのになぜそれが機能するのか疑問に思っています...

通常、「分割統治」アルゴリズムが非分割統治アルゴリズムよりもうまく機能するのはなぜですか?

マスターの定理では、次のT(n) = a*T(n/b) + f(n)3 つのケースを使用しています。

1. a*f(n/b) = c*f(n)ある一定c > 1の場合T(n) = (n^log(b) a)
2. もしそうa*f(n/b) = f(n)ならT(n) = (f(n) log(b) n)
3. a*f(n/b) = c*f(n)ある一定c < 1の場合T(n) = (f(n))

しかし、f(n) = log nまたはの場合n*log n、 の値cは n の値に依存します。マスターの定理を使用して再帰関数を解くにはどうすればよいですか?

の 2 次元平面上の n 個の点の集合が与えられた場合(x,y)、その目的は、2 つの点を結ぶ線が負の勾配を持つようなすべての点(xi,yi)のペアの数を見つけることです。(xj, yj)

xi2 つの が同じ値を持たないと仮定します。[-100,100]すべてのポイントが、またはその他の範囲内にあると仮定します。

欲張りアルゴリズムとバック トラッキング アルゴリズムの両方を使用して、バック トレース アルゴリズムを実装しました。バック トラッキング アルゴリズムは次のとおりです。

貪欲なアルゴリズムは、次数が最小のノードを繰り返し選択し、MIS に配置してから、そのノードとその隣接ノードを G から削除します。

エッジが存在する確率が 0.5 であるさまざまなグラフ サイズでアルゴリズムを実行した後、経験的に、バック トラッキング アルゴリズムは貪欲アルゴリズムよりも小さい最大独立集合を常に検出することがわかりました。これは期待されていますか？