Рішення головоломки Ж. АРСАКОВ
Виконала учениця 11 А класу Коробова Тамара
Аркадіївна
Муніципальне загальноосвітній установа "Ліцей № 43»
Саранськ, 2004
Моя
робота буде присвячена вирішенню головоломки, умова якої знаходиться в книзі
Ж. АРСАКОВ «Програмування ігор і головоломок».
Умова
головоломки таке:
Вибрали
два натуральних числа великі 1 і менші 100. Значення їх твори повідомили
пану Р, а значення суми - пану S (причому, жоден з них не знає
яке число повідомили іншому). Далі між паном Р і паном S
відбувся такий діалог:
Пан
Р: Я не можу знайти ці два числа.
Пан
S: Я знаю, що Вам це і не вдалося б.
Пан
Р: Ах так. Ну тоді я їх знаю.
Пан
S: Ну тоді і я теж їх знаю.
Цим
діалогом загадані числа «обчислюються» однозначно.
Я
склала програму на мові Pascal, яка «аналізує» висловлювання
пана Р і пана S і тому, природно, складається з 4 частин:
1)
перша «відкидає» пари, що складаються з простих чисел;
2)
другий «відкидає» з решти пар такі, сума яких може бути
представлена у вигляді двох простих доданків;
3)
третя - ті пари чисел, твір яких зустрічається у який-небудь інший
пари чисел, яка, до речі, теж буде відкинута;
4)
четверта - ті пари чисел, сума яких зустрічається у якої-небудь іншої пари
чисел, яка, до речі, теж буде відкинута.
Тепер
про саму програму: для зберігання інформації про пари чисел я використовую двовимірний
булевський масив b, в який на відповідні місця я буду записувати
«Істину», якщо пара чисел задовольняє умові задачі на даному кроці і,
природно, «брехня», якщо - ні. До речі, щоб числа i, j і j, i не вважалися
двічі перебір йде тільки по половині таблиці.
Булевського
процедура prost буде «істиною», якщо число х - просте і «брехнею», якщо --
складене.
Решта
пояснення знаходяться в ремарка самої програми.
const n = 99;
m = (n-1) * n div 2;
var b: array [2 .. 250,2 .. 250] of
boolean;
i, j, k, l, p, vs1, vs2, vs3, vs4, sum, s:
word;
fin: boolean;
function prost (x: word): boolean; (істина, якщо х - просте число)
var da: boolean;
p: word;
begin
da: = true;
if x> 2 then
for p: = 2 to trunc (sqrt (x)) do if
x = (x div p) * p then da: = false;
prost: = da;
end;
begin
(починається
перший крок - будуть відкинуті ті пари чисел,
у
яких обидва числа - прості)
writeln ( 'при n =', n);
vs1: = 0;
(vs1 - кількість рішень після першого кроку)
for i: = 2 to n do
for j: = i to n do
begin
if prost (i) and prost (j) then
b [i, j]: = false
else begin b [i, j]: = true; vs1: = vs1 1;
end;
end;
writeln ( 'vs1 =', vs1: 5, 'iz', m);
s: = 0;
(s-кількість рішень, які будуть відкидатися надалі)
(починається
другий крок - будуть відкинуті ті пари чисел i, j, сума яких
може
бути представлена у вигляді двох простих доданків)
for i: = 2 to n do
for j: = i to n do
begin
if b [i, j] then
begin
sum: = i + j; fin: = false; k: = 2;
while (not fin) and (k <= (sum div
2)) do
begin
if prost (k) and prost (sum-k) then
fin: = true;
k: = k +1;
end;
if fin then begin b [i, j]: = false;
s: = s +1; end;
end;
end;
vs2: = vs1-s; writeln ( 'vs2 =', vs2: 5, '
iz ', m);
(починається
третій крок - будуть відкинуті ті пари чисел i, j, твір
яких
зустрічається у якої-небудь іншої пари чисел, яка, до речі,
теж буде відкинута)
for i: = 2 to n do
for j: = i to n do if b [i, j] and
(i = 98) and (j = 99) then writeln (i: 3, j: 3);
for i: = 2 to n do
for j: = i to n do
begin
if b [i, j] then
begin
p: = i * j; fin: = false; k: = 2;
while k <= n do
begin
l: = k;
while l <= n do
begin
if b [k, l] and (p = k * l) and
(i <> k) then
begin fin: = true; b [k, l]: = false;
s: = s +1; end;
l: = l +1;
end;
k: = k +1;
end;
if fin then begin b [i, j]: = false;
s: = s +1; end;
end;
end;
vs3: = vs1-s; writeln ( 'vs3 =', vs3: 5, '
iz ', m);
(починається
четвертий крок - будуть відкинуті ті пари чисел i, j, сума
яких
зустрічається у якої-небудь іншої пари чисел, яка, до речі,
теж буде відкинута)
for i: = 2 to n do
for j: = i to n do
begin
if b [i, j] then
begin
sum: = i + j; fin: = false; k: = 2;
while k <= n do
begin
l: = k;
while l <= n do
begin
if b [k, l] and (sum = k + l) and
(i <> k) then
begin fin: = true; b [k, l]: = false;
s: = s +1; end;
l: = l +1;
end;
k: = k +1;
end;
if fin then begin b [i, j]: = false;
s: = s +1; end;
end;
end;
vs4: = vs1-s; writeln ( 'vs4 =', vs4: 5, '
iz ', m);
for i: = 2 to n do
for j: = i to n do if b [i, j] then
writeln (i: 4, j: 4);
readln
end.
Тепер
про результати:
1)
виявляється при тих умовах, які повідомлені у книзі (числа більше 1 і менше
100, тобто від 2 до 99 включно, тому спочатку у програмі константа
n = 99) завдання має два рішення:
(4; 13)
і (98; 99);
2)
але якщо умови змінити: числа від 2 до 100 включно, то друге рішення
(98; 99) відкидається на 4 кроці, тому що є дві пари чисел з такою сумою:
(98; 99) і (97; 100).
Всі
це спонукало мене досліджувати цю задачу більш детально: за яких ще
значеннях n це завдання буде мати єдине рішення.
Досить
видозмінити наведену програму (n тепер буде не константою, а змінної
і взяти всю програму всередину циклу з цієї змінної від 5 до 110).
Результати
виявилися такі:
При
достатньо малих значеннях n (n <35) завдання або не мала рішення (при n = 5,
7, 8, 10, 11, 13, 16, 17, 20, 22, 23, 25, 28, 31, 32), або мала тільки одне
рішення рівне числах (n-1) і n (при n = 6, 9, 12, 14, 15, 18, 19, 21, 24, 26,
27, 29, 30, 33, 34).
При
n = 35 стався якісний стрибок: тепер рішення були завжди, причому при
деяких значеннях n (при n = 35, 37, 38, 41, 43, 46, 50, 52, 53, 55, 56, 58,
65, 67, 70, 71, 76, 77, 80, 83, 85, 88, 91, 92, 97, 98, 100, 101, 107) це було
єдине рішення однакове для всіх n: (4; 13), а при інших значеннях
n> 35 додавалося ще одне рішення: (n-1; n).
Список літератури
Ж. Арсак,
«Програмування ігор і головоломок», М., Наука, 1990р.
Для
підготовки даної роботи були використані матеріали з сайту http://licey43.ru
