最近、Habréで興味深い仕事が2人の賢者について語られました。 ここでは、独自のバージョンのソリューションを提供し、このソリューションに到達する方法を説明します。 条件を思い出させてください：
いくつかのスルタンには、アリ・イブン・ワリとワリ・イブン・アリという2つの賢者がいました。 スルタンは彼らの知恵を確信させたいと思い、賢者を自分自身に呼び、こう言いました。 両方とも完全で、それぞれが1つ以上、100未満です。 これらの数値を掛けて、結果をアリに通知します。バリの間、これらの数値の合計を言います。 彼らがあなたについて言っているのと同じくらい賢明であれば、最初の数字を見つけることができます。
スルタンはアリを作品、バリを合計と言いました。 賢者は考えました。 アリは沈黙を破った最初の人でした。
「私はこれらの数字を知りません」と彼は頭を下げて言った。
「私はそれを知っていました」と、ヴァリは言いました。
「それからこれらの数字を知っています」とアリは喜んだ。
-わかった！ -バリを叫んだ。
そして、賢者は、彼が想像した数字を打たれたスルタンに知らせた。
これらの数字は何ですか？
同様のタスクがHabréにもありました。 はるかに簡単です。
誕生日タスク：
アルバートとバーナードはちょうどシェリルに会った。 彼らは彼女の誕生日がいつか知りたい。 シェリルは、10の可能な日付を提供しました。5月15日、5月16日、5月19日、6月17日、6月18日、7月14日、7月16日、8月14日、8月15日、8月17日。 それからシェリルはアルバートに彼女の誕生月、そしてバーナードにその日を話しました。 その後、対話が行われました。
アルバート：シェリルの誕生日がいつかはわかりませんが、バーナードも知らないことは知っています。
バーナード：最初は、シェリルの誕生日がいつだったかは知りませんでしたが、今は知っています。
アルバート：シェリルが誕生日を迎えたときも知っています。
シェリルの誕生日はいつですか？
よく見ると、これら2つのタスクは完全に同一であることがわかります。
いくつかの作品がいくつかの金額に対応するように、いくつかの日はいくつかの可能な月に対応します（たとえば、製品60には15 + 4 = 19、12 + 5 = 17などの金額が対応します）。 いくつかの月は数日間に対応し、いくつかの作品はいくつかの合計に対応します（たとえば、合計10は作品6 * 4 = 24、7 * 3 = 21などに対応します）。 対話の意味もまったく同じです。
これは、誕生日の問題を解決するための実用的なアルゴリズムを作成すれば、賢者の問題にそれを使用できることを意味します。 違いは、可能な日月の組み合わせの数と、整理する量と製品だけです。 誕生日を紙で手動で計算できる場合、1〜100の数字を検索するには、ソフトウェアツールを使用する必要があります。 そのため、最初に単純なタスクのアルゴリズムを作成してそれが正しいことを確認し、次に、より複雑なものから初期データを置き換えます。
ソリューションでは、MATLABを使用しました。 はい、大砲からスズメを撃ちますが、職場でMatlabによく会うので、誰もが彼に馴染みのあるツールを使用できるようにします。
解決策です。
1.初期条件を記述します：日の可能な値を持つベクトル、月の可能な値を持つベクトル、および可能な組み合わせの場所にユニットがある長方形のマトリックス。
days = [14; 15; 16; 17; 18; 19]; months = [5; 6; 7; 8]; matrix = [ 0 0 1 1; 1 0 0 1; 1 0 1 0; 0 1 0 1; 0 1 0 0; 1 0 0 0 ];
2.月を知っているアルバートの最初のフレーズを分析しましょう。
シェリルが誕生日を迎える時期はわかりませんが、バーナードも誕生日を知りません。このことから、今月に許可されている日は1か月以上に対応していると結論付けることができます。
この状況は、5月（誕生日が5月19日の場合、バーナードが既に答えを知っているため）および6月（答えが6月18日の場合、バーナードも正確な日付を知っているため）不可能です。
不可能な月を除外するには、ユニットが1つしかない行（18日目と19日目）を見つけ、これらのユニットがある列（5日目と6日目）を見つけ、これらの列を消す必要があります。
Matlabでは、このアクションは次のようになります。
unique_days = find(sum(matrix,2)==1); [~, months_with_unique_days] = find (matrix(unique_days,:)==1); months_with_unique_days = unique(months_with_unique_days); matrix(:,months_with_unique_days) = []; months(months_with_unique_days) = [];
3.最初の文の後、その日を知っているバーナードは答えた：
シェリルが誕生日を迎えたのは最初は知りませんでしたが、今は知っています。
これは、バーナードが知っている日がたった1か月であることを意味します。
この状況は、番号15、16、および17で発生する可能性があります。
複数のソリューションがあるか、またはないソリューションのマトリックスのすべての行を削除する必要があります。
non_unique_days = find(sum(matrix,2)~=1); matrix(non_unique_days,:) = []; days(non_unique_days) = [];
4.月を知っているアルバートは答えました：
シェリルが誕生日を迎える時期もわかりました。そのため、マトリックスの残りの部分には、オプションが1つしかない列が残っています。 この列は7月に対応しています。 複数のオプションがあるすべての列を破棄します。
non_unique_months = find(sum(matrix)~=1); matrix(:,non_unique_months) = []; months(non_unique_months) = [];
5.残りの列でユニットを見つけることは残ります。
days = days(matrix == 1); disp(days); disp(months);
回答： 7月16日 。
完全なソリューションソースコードを次に示します。
% Birthday example matrix = [ 0 0 1 1; 1 0 0 1; 1 0 1 0; 0 1 0 1; 0 1 0 0; 1 0 0 0 ]; days = [14; 15; 16; 17; 18; 19]; months = [5; 6; 7; 8]; % Remove months with unique days unique_days = find(sum(matrix,2)==1); [~, months_with_unique_days] = find (matrix(unique_days,:)==1); months_with_unique_days = unique(months_with_unique_days); matrix(:,months_with_unique_days) = []; months(months_with_unique_days) = []; % Remove non-unique days non_unique_days = find(sum(matrix,2)~=1); matrix(non_unique_days,:) = []; days(non_unique_days) = []; % Find 1 month with unique day non_unique_months = find(sum(matrix)~=1); matrix(:,non_unique_months) = []; months(non_unique_months) = []; % Find the last day days = days(matrix == 1); % Result output disp(days); disp(months);
では、このアルゴリズムを賢者の問題に適用してみましょう。
月は2〜99の2つの数字のすべての可能な合計に置き換えられます。これらは4〜198の整数です。日は2〜99の2つの数字のすべての製品に置き換えられます。可能な和と積のペアの交差。
このテーブルの小さな断片（約1/400）
横軸は合計、縦軸は積です。
months = 4:198; days = unique((2:99)'*(2:99)); matrix = false(length(days),length(months)); for i1 = 2:99 for i2 = 2:99 matrix(days==(i1*i2),months==(i1+i2)) = true; end; end;
プログラムを実行して答えを得る：製品は52、合計は17です。
これは数字のペア4と13に対応します。