2つの賢者の問題。 解決するコンピュータープログラム

2つの賢者の問題は長年さまざまなフォーラムで浮上してきており、それ自体への関心を絶えず更新しています。 条件を思い出させてください:

いくつかのスルタンには、アリ・イブン・ワリとワリ・イブン・アリという2つの賢者がいました。 スルタンは彼らの知恵を確信させたいと思い、賢者を自分自身に呼び、こう言いました。 両方とも完全で、それぞれが1つ以上、100未満です。 これらの数値を掛けて、結果をアリに通知します。バリの間、これらの数値の合計を言います。 彼らがあなたについて言っているのと同じくらい賢明であれば、最初の数字を見つけることができます。

スルタンはアリを作品、バリを合計と言いました。 賢者は考えました。 アリは沈黙を破った最初の人でした。

「私はこれらの数字を知りません」と彼は頭を下げて言った。

「私はそれを知っていました」と、ヴァリは言いました。

「それからこれらの数字を知っています」とアリは喜んだ。

-わかった! -バリを叫んだ。

そして、賢者は、彼が想像した数字を打たれたスルタンに知らせた。

これらの数字は何ですか?


特定の最大数に対してこのような問題を解決できる既製のコンピュータープログラムは見つかりませんでした。 だから私は自分で同様のプログラムを書くことにしました。 最大数が100に等しい古典的な問題の例として、解法アルゴリズムを説明します。



1.私はこれらの数字を知らない、2つの数字の積を知っている賢者は言った



したがって、この製品は2つの数値の積として明確に表すことはできません。 他の数字のペアでこの製品を入手する方法は少なくともいくつかありますが、これらの数字は両方とも100未満であるという条件を満たす必要があります。1つの方法でしか表現できない作品は、将来的にユニークと呼ばれます。



この声明から、これらの数値のいくつかの特性について結論づけることができます。 まず、両方を同時に単純にすることはできません。そうでなければ、それらの製品は一意であり、これらの2つの素数の製品としてのみ表現できます。 この条件は必要ですが、作品の独自性にとって十分な条件ではありません。 将来的には、2つの素数の積ではない他のユニークな作品を見つけるでしょう。



2.私はそれを知っていた、2つの数字の合計を知っている賢者は言った



2つの数値Sの合計は、2 +(S-2)、3 +(S-3)など、さまざまな方法で1組の数値で表すことができます。



このステートメントは、これらの数値のペアがどれも互いに乗算されても、一意の積を与えないことを示しています。 2つの数値の合計にそのようなプロパティがあるかどうかを判断してみましょう。 2つの数値の和の候補のリストを作成します。



まず、すでに示したように、2つの数を両方とも素数にすることはできません。したがって、それらの合計を2つの素数の合計にすることはできません。 そのため、コンピュータープログラムは、最初に、指定された最大数より少ないすべての素数のリストを計算します。 さらに、彼はこれらの素数によって得られる可能性のあるすべての合計を見つけ、それらをさらなる研究から除外します。 その結果、最初の近似-可能な量を取得します。



11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 101 103105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153155157159161161163165167169171171173174175177177179181182182183184185187187188189190191192193195196



原則として、これらすべての可能な量の一意性をすぐに確認できます。 つまり 合計ごとに、可能なすべての数字のペアを構成し、これらの数字の積が一意であることを確認します。 調査中の合計に対して少なくとも1組の数値が一意の製品を提供する場合、この金額は候補から削除されます。 作品の独自性をチェックするこのルーチンは、プログラム全体の中で最も難しい部分です。 そのようなプログラムを作成しようとした多くの人は、単にそれを忘れてしまい、正しい結果を得られませんでした。



このサブプログラムでは、最初に調査対象の製品が単純な要因に分割され、次にこれらの単純な要因から取得できるすべての可能な製品のリストがコンパイルされます。これが最初の要因です。 製品を最初の係数で除算することで2番目の係数を取得し、最初の係数が2番目の係数より小さい場合にのみオプションをチェックします。 次に、両方の要因が問題の条件を満たしているかどうかを確認します(両方とも最大数100未満であるか、合計がMax未満です)。 したがって、製品の2つの要素への許容可能な分解を取得します。そのような分解が1つしかない場合、この製品は一意です。



しかし、一意性のチェックを開始する前に、不必要な計算でコンピューターをロードしないようにタスクを単純化します。 あまり明白ではないプロパティを使用します-最大値はいくらですか。

調査対象の製品の素因数が50を超える場合(Maxの半分以上、この場合は素数53)、この製品は一意です。 2番目の分解オプションを取得しようとすると、少なくとも53を2倍して100より大きい係数を取得する必要があるためです。



53 + 2を超える合計Sの場合、数値53とS-53のペアを見つけることができ、これらの数値の積は一意になります。 このことから、55を超えるすべての金額を今後の計算から除外できると結論付けました。

これにより、検索が11の可能な量に絞り込まれます。



11 17 23 27 29 35 37 41 47 51 53



次に、可能なすべての数字のペアの積の一意性を確認します。 このプログラムは、マイナス記号付きのユニークな作品を表示します。



1:X + Y = 11、X * Y =:18 24 28 30

2:X + Y = 17、X * Y =:30 42 52 60 66 70 72

3:X + Y = 23、X * Y =:42 60 76 90102112120126130132132

4:X + Y = 27、X * Y =:50 72 92110126140152162170170176180182

5:X + Y = 29、X * Y =:54 78100120138 154168180190198204208210

6:X + Y = 35、X * Y =:66 96124150174174196216234250264276286294300304306

7:X + Y = 37、X * Y =:70102132160186210232232252270286300312322330336340340342

8:X + Y = 41、X * Y =:78 114 148 180 210 238 264 288 310 330 330 348 364 378 390 400 408 414 418 420

9:X + Y = 47、X * Y =:90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 552

10:X + Y = 51、X * Y =:98 144 188 230 270 308 344 378 410 440 468 494 518 540 560 -578 594 608 620 630 638 644 648 650

11:X + Y = 53、X * Y =:102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612 630 646 660 672 682 690 696 700 702



1つのユニークな作品が発見されました-578 = 2 * 17 * 17。 実際、この数は1つの方法でしか表現できません-17 * 34、2番目の方法2 * 289は条件を満たしません-両方の数は100未満です。



したがって、金額51も候補から削除され、許容される金額は10のみになります。



ちなみに、プログラムのおかげで、ユニークな作品を発見する方法に関する次の簡単なルールを簡単に見つけることができます。



製品の形式が2 * P * P(Pは最大数(100)よりも大きい平方の素数)である場合、この製品は一意であり、2つの数Pと2 * Pの合計に対応し、この合計は3 * Pです。



したがって、3 * P(Pは10より大きい素数)であるすべての金額を消すことができます。この場合、これは合計51 = 3 * 17です。



プログラムのさらなる作業により、ユニークな作品の他の興味深いルールが明らかになりました...



したがって、セージの最初の2つのレプリカの後、最初のセージは2つの数字の合計が10個の数字のうちの1つにしかなれないことを知っています。



11 17 23 27 29 35 37 41 47 53



3.それからこれらの数字を知っている-アリは喜んだ



どちらの場合、アリは自分の作品を分解する数字のペアを一意に決定できますか? その合計はこれらの10の合計の1つに等しく、1組の数値だけがこのセットの合計を持ちます。 コンピューターアルゴリズムの観点からは、複数回発生する作業は削除する必要があります。 たとえば、積30は2回発生します-11の合計と17の合計で、アリに番号30が伝えられた場合、2つの数のペアが問題の条件を満たすことがわかります。5、6(合計11)および2、15(合計17 )そして彼は明確に言うことができませんでした-私はこれらの数字を知っています。 そのため、重複する作品はすべて削除されます。 その結果、次の図が表示されます-すべての許容量と、これらの量のすべての許容製品:



1:X + Y = 11、X * Y =:18 24 28

2:X + Y = 17、X * Y =:52

3:X + Y = 23、X * Y =:76 112 130

4:X + Y = 27、X * Y =:50 92 110 140 152 162 170 176 182

5:X + Y = 29、X * Y =:54100138154168168190198204208

6:X + Y = 35、X * Y =:96 124 174 216 234 250 276 294 304 306

7:X + Y = 37、X * Y =:160186232252252270336340

8:X + Y = 41、X * Y =:114 148 238 288 310 348 364 378 390 400 400 408 414 418

9:X + Y = 47、X * Y =:172 246 280 370 442 480 496 510 522 532 540 550 552

10:X + Y = 53、X * Y =:240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696 700 702



4.それでわかった! -叫んだバリ



3番目のレプリカの後、Valiは私たちと同じようにすべてのコンピューティング作業を行い、すべての繰り返し部分を破棄しました。 そして、彼の合計に対して、有効な製品が1つだけ残っている場合にのみ、彼は一意に数値を決定できます。 コンピューターの観点から見ると、1行に有効なピースが1つだけ残っています。 私たちの場合、これは17の合計に対する52の積であり、これは数字のペア4、13に対応します。このソリューションは唯一のものです。



私のコンピュータープログラムでは、最大数の任意の値のタスクの結果を取得できます。

このタスクにはさまざまなバリエーションがあります。

-両方の数値が指定した値よりも小さい

-数の合計が指定された最大数より少ない。

-数字は同じかもしれません。

-数字は必然的に異なります。

プログラムでは、これらすべてのバリエーションの結果を計算できます。

プログラムは、計算の各段階の中間結果を出力できます。

指定された数値範囲に対して新しい解が現れる境界点をすべて計算することもできます。 たとえば、2000までのすべての数値をスキャンすると、次の結果が得られます。



最大= 10の結果

結果なし



最大= 63の結果

1:X = 4、Y = 13



最大= 867の結果

1:X = 4、Y = 13

2:X = 4、Y = 61



最大= 1503の結果

1:X = 4、Y = 13

2:X = 4、Y = 61

3:X = 32、Y = 131



最大= 1967の結果

1:X = 4、Y = 13

2:X = 4、Y = 61

3:X = 16、Y = 73

4:X = 32、Y = 131



計算の終わり。 計算時間:0:00:29



ソリューション4、13は、63〜866の範囲で一意であることがわかります。



ちなみに、「Science and Life」というジャーナルに掲載されたタスクには、数が60未満という条件があったため、まったく解決策がありません。読者が問題を解決しようとして台無しになった期間は想像できますが、正しい解決策はありません



可能であれば、プログラムリストとプログラム自体(Delphiで記述)をレイアウトする準備ができています。



All Articles