バイナリ値を使用してハノイの塔の問題を解決するC++プログラム
このC++プログラムは、バイナリ値を使用してハノイの塔の問題の解決策を表示します。
ディスクごとに1桁の2進数があります。
最上位ビットは最大のディスクを表します。値0は、最大のディスクが最初のペグにあることを示し、1は、それが最後のペグにあることを示します。
ビット文字列は左から右に読み取られ、各ビットを使用して、対応するディスクの場所を判別できます。
ビットの値が前のディスクと同じである場合、対応するディスクは同じペグ上の前のディスクの上にスタックされます。
異なる場合は、対応するディスクが前のディスクの1つ左または右にあることを意味します。
アルゴリズム
Begin Take the number of disk n as input. Declare n and a. Make a for loop a = 1 to (1<<n) – 1 // Here, (a & a – 1) = bitwise AND with a and a – 1. (a | a – 1) = bitwise OR with a and a – 1. Here % means modulus operator. // Print the result indicating that moving disks from peg number (a & a – 1) % 3 to peg number ((a | a – 1) + 1) % 3 End
例
#include<iostream>
using namespace std;
int main() {
int n, a;
cout<<"\nEnter the no of Disks: ";
cin>>n;
for (a = 1; a < (1 << n); a++) {
cout<<"\nDisk Move from Peg "<<(a&a-1)%3 <<" to Peg "<<((a|a-1)+1)%3;
}
cout<<"\n";
} 出力
Enter the no of Disks: 3 Disk Move from Peg 0 to Peg 2 Disk Move from Peg 0 to Peg 1 Disk Move from Peg 2 to Peg 1 Disk Move from Peg 0 to Peg 2 Disk Move from Peg 1 to Peg 0 Disk Move from Peg 1 to Peg 2 Disk Move from Peg 0 to Peg 2
-
C ++プログラムでの二分探索？
二分探索は、半区間探索、対数探索、または二分探索とも呼ばれ、ソートされた配列内のターゲット値の位置を見つける検索アルゴリズムです。二分探索は、ターゲット値を配列の中央の要素と比較します。それらが等しくない場合、ターゲットが存在できない半分が削除され、残りの半分で検索が続行され、再び中央の要素がターゲット値と比較され、ターゲット値が見つかるまでこれが繰り返されます。残りの半分が空の状態で検索が終了した場合、ターゲットは配列に含まれていません。アイデアは単純ですが、バイナリ検索を正しく実装するには、特に配列の値が範囲内の整数のすべてではない場合、終了条件と中間点の計算に関する微妙な点に注意する必要
-
動的計画法を使用してナップサック問題を解決するC++プログラム
これは、動的計画法を使用して0-1ナップサック問題を解決するC++プログラムです。 0-1ナップサック問題では、それぞれに重みと値を持つアイテムのセットが与えられます。合計重量が指定された制限以下になり、合計値が可能な限り大きくなるように、コレクションに含める各アイテムの数を決定する必要があります。 アルゴリズム Begin Input set of items each with a weight and a value Set knapsack capacity Create a function that returns maximum of two integers. Create a