Типа пятничная задачка

← →
Sha © (2013-07-13 13:12) [40]

procedure TForm1.Button1Click(Sender: TObject); const min= 3; max= 100; var x, y, z: integer; MulPairCount, KnownPairCount, HardSumCount, KnownProdCount: array of integer; begin; SetLength(MulPairCount, 1 + max*max); for z:=0 to max*max do MulPairCount[z]:=0; for x:=min to max do for y:=x to max do inc(MulPairCount[x*y]); SetLength(KnownPairCount, 1 + max+max); for z:=0 to max+max do KnownPairCount[z]:=0; for x:=min to max do for y:=x to max do if MulPairCount[x*y]=1 then inc(KnownPairCount[x+y]); SetLength(HardSumCount, 1 + max*max); for z:=0 to max*max do HardSumCount[z]:=0; for x:=min to max do for y:=x to max do if KnownPairCount[x+y]=0 then inc(HardSumCount[x*y]); SetLength(KnownProdCount,1 + max+max); for z:=0 to max+max do KnownProdCount[z]:=0; for x:=min to max do for y:=x to max do if HardSumCount[x*y]=1 then inc(KnownProdCount[x+y]); Memo1.Lines.Clear; for x:=min to max do for y:=x to max do if (MulPairCount[x*y]>=2) and (KnownPairCount[x+y]=0) and (HardSumCount[x*y]=1) and (KnownProdCount[x+y]=1) then Memo1.Lines.Add(Format("(%d,%d) %d %d %d %d", [x, y, MulPairCount[x*y], KnownPairCount[x+y], HardSumCount[x*y], KnownProdCount[x+y] ])); end;

← →
картман © (2013-07-13 15:23) [41]

> Sha © (13.07.13 13:12) [40]

круто!

А вот это:
Memo1.Lines.Clear; for x:=min to max do for y:=x to max do if (MulPairCount[x*y]>=2) and (KnownPairCount[x+y]=0) //- не излишня ли проверка
, учитывая
for x:=min to max do for y:=x to max do if MulPairCount[x*y]=1 then inc(KnownPairCount[x+y]);

?

← →
Sha © (2013-07-13 15:31) [42]

> картман © (13.07.13 15:23) [41]
> не излишня ли проверка

попробуй ее закомментировать - узнаешь )

← →
картман © (2013-07-13 15:38) [43]

> попробуй ее закомментировать - узнаешь )

))

← →
Компромисс1 © (2013-07-13 17:09) [44]

> (13,16)

Если это верный ответ, то у меня претензия к топик-стартеру: надо сразу было писать, чтобы не пытались решить без компьютерной программы.

← →
Sha © (2013-07-13 18:01) [45]

почти все задачи на перебор не для человека

← →
Очень злой (2013-07-14 08:53) [46]

> Sha © (13.07.13 12:51) [39]
>
> (13,16)

Да.

> Компромисс1 © (13.07.13 17:09) [44]
>
>
> > (13,16)
>
>
> Если это верный ответ, то у меня претензия к топик-стартеру:
> надо сразу было писать, чтобы не пытались решить без компьютерной
> программы.

Ну так я же написал задачку на форуме программистов. )

Не, ну можно и вручную решать, потратится только много времени и бумаги. Но программисты - на то они и программисты, чтобы для долгих, нудных и тупых вычислений использовать комп, а мозги занять чем-то более умным и интересным, т.е. написанием самой программы...

← →
Юрий Зотов © (2013-07-14 23:39) [47]

> султан сообщил первому визирю произведение этих чисел,
> а второму - их сумму.
> Первый визирь подумал и говорит:

Какое число назвал тебе султан?

Получив ответ, первый визирь решает систему двух уравнений с двумя неизвестными:
x+y=s
x*y=m
и называет оба числа.

← →
Юрий Зотов © (2013-07-15 00:48) [48]

Таким образом, при любых S и M решений не может быть больше двух (это к вопросу о недоопределенности задачи).

← →
Компромисс1 © (2013-07-15 10:35) [49]

- Я загадал два числа A и B от 3 до 100. Вы должны их мне назвать. При этом султан сообщил первому визирю произведение этих чисел P, а второму - их сумму S.Первый визирь подумал и говорит: - Я не знаю что это за числа

1) P является произведением более чем двух пар чисел от 3 до 100 (далее не пишу от 3 до 100)

На что второй ответил: - Я был в этом уверен.

2) S является суммой более чем двух пар чисел, произведение каждой пары является произведением более чем двух пар чисел от 3 до 100

> Тогда первый говорит:
> - В таком случае, я знаю, что это за числа.

3) Только одна пара чисел из 1) обладает свойством 2)

Второй: - Тогда и я знаю, что это за числа.

4) Только одна пара чисел из 2) обладает своством 3)

← →
Компромисс1 © (2013-07-15 10:36) [50]

Вместо "более чем двух пар" везде должно стоять "более чем одной пары"

← →
Sha © (2013-07-15 10:39) [51]

Судя по всему, тут кое-кого не устраивает формулировка задачи)
Позволю себе немного ее подредактировать.

У одного султана было 2 мудреца и кандидат на место третьего - ты.
Захотел он проверить твою сообразительность.

Позвал к себе мудрецов и кандидата и сказал всем троим:
- Я загадал два числа от 3 до 100. Первому мудрецу я прошепчу на ухо
произведение этих чисел, второму - сумму.

Сделал он так, потом спрашивает второго мудреца:
- Как ты думаешь, если бы мой первый вопрос был бы задан первому
мудрецу, смог ли он назвать мне задуманные числа?
- Нет.

Тогда султан спрашивает первого мудреца:
- Можешь ли ты назвать эти числа?
- Да.

Затем султан спрашивает второго:
- Можешь ли ты назвать эти числа?
- Да.

Затем султан обращается к тебе:
- Назови мне зти числа или я прикажу отрубить тебе голову!

← →
Очень Злой (2013-07-15 10:45) [52]

> Sha © (13.07.13 13:12) [40]

Я так делал:
var min,max:integer; ... // Реплика 1. Первый визирь не знает числа. // Следовательно произведение имеет более одного варианта разложения // на множители удовлетворяющие условию задачи // // функция возвращает true - если произведение имеет один вариант разложения function IsP1(num:integer):boolean; var i:integer; count:integer; begin count:=0; for i:=min to trunc(sqrt(num)) do if (num mod i = 0) and (num div i <= max) then inc(count); result:=count=1; end; // реплика 2. Второй визирь уверен в том что первый не знал числа. // Следовательно названная ему сумма ни каким образом не может быть разложена // на слагаемые, удовлетворяющие условию задачи, // на произведение которых ранее описанная функция IsP1() выдала бы true. // // Для такой суммы возвращается true function IsS1(num:integer):boolean; var i:integer; begin result:=true; for i:=min to num div 2 do if (num-i<=max) and isp1(i*(num-i)) then begin result:=false; break; end; end; // реплика 3. Первый визирь говорит что он знает числа. // Следовательно произведение чисел среди всех своих вариантов разложения // имеет один и только один вариант разложения на множители удовлетворяющие условию задачи // для суммы которых ранее описанная функция IsS1() даст true // // для таких произведений возвращаем true function IsP2(num:integer):boolean; var i:integer; count:integer; begin count:=0; if not IsP1(num) then for i:=min to trunc(sqrt(num)) do if (num mod i = 0) and (num div i <= max) and IsS1(i+(num div i)) then inc(count); result:=count=1; end; // Реплика 4. Второй визирь сказал что тоже знает числа. // Следовательно сумма имеет один и только один вариант разложения на слагаемые удовлетворяющие условию задачи // для произведения которых ранее описанная функция IsP2 дает true // // для таких сумм возвращаем строку с обоими числами, иначе пустую строку function IsS2(num:integer):string; var i,count:integer; begin count:=0; if IsS1(num) then for i:=min to num div 2 do if (num-i<=max) and isp2(i*(num-i)) then begin inc(count); result:=inttostr(i)+" "+inttostr(num-i); end; if count<>1 then result:=""; end; // ну и наконец-то сам перебор сумм и вывод результата procedure TForm1.Button1Click(Sender: TObject); var k:integer; p:string; begin min:=SpinEdit1.Value; // минимальное значение чисел max:=SpinEdit2.Value; // максимальное значение чисел // перебираем все возможные суммы двух чисел for k:=min+min to max+max do begin p:=iss2(k); if length(p)>0 then Memo1.Lines.Add(p); end; end;

← →
Sha © (2013-07-15 11:00) [53]

> Очень Злой (15.07.13 10:45) [52]
> Я так делал:

Считает долго, наверное?

Я с самого начала нацелился на массивы, т.к. предполагал,
что будет сильная зависимость решения от диапазона разрешенных чисел.

Результат оказался даже интереснее, чем я мог ожидать.
С увеличением верхней границы новые решения не только появляются,
но и исчезают...

← →
Очень Злой (2013-07-15 11:09) [54]

> Считает долго, наверное?

Совсем нет. по крайней мере визуально не заметно задержки...

Пробовал GetTickCount, но разница между его значением после расчетов и до расчетов обычно равна 0

← →
Sha © (2013-07-15 11:13) [55]

Я свою гонял с небольшим шагом до переполнения памяти (max=12000),
увидел много интересного.

С вложенными вызовами такое вряд ли удалось бы в преемлемое время)

← →
Очень Злой (2013-07-15 11:17) [56]

> Sha © (15.07.13 11:13) [55]
>
> Я свою гонял с небольшим шагом до переполнения памяти (max=12000),
>
> увидел много интересного.

Ну у меня если max увеличивать - то да, время вычислений начинает быть заметным. 12000 не пробовал... наверное действительно будет долго...

← →
Визирь 3 (2013-07-17 10:01) [57]

> - Я загадал два числа от 3 до 100. Вы должны их мне назвать.

А султан загадывает разные числа или может загадать и два одинаковых? Например 22 и 22.

← →
Sha © (2013-07-17 10:35) [58]

Ты должен исходить из того, что он может загадать любые в указанном интервале.

Но т.к. числа загадываются им для проверки твоей сообразительности,
то это существенно ограничивает выбор султана.

В задаче тебе предлагается найти все возможные пары чисел,
которые может выбрать султан.

← →
Дмитрий СС (2013-07-17 10:38) [59]

Как вы формализовали две последних реплики?

← →
Sha © (2013-07-17 10:39) [60]

И, мне кажется, лучше использовать условия задачи из [51].
В такой формулировке они понимаются однозначно.

← →
Sha © (2013-07-17 10:44) [61]

> Дмитрий СС (17.07.13 10:38) [59]
> Как вы формализовали две последних реплики?

Выбирай, что больше нравится:

Sha © (13.07.13 13:12) [40]
Компромисс1 © (15.07.13 10:35) [49, 50]
Очень Злой (15.07.13 10:45) [52]

В любом из этих постов смотри 2 последних куска текста)

← →
Визирь 3 (2013-07-17 10:51) [62]

> Sha © (17.07.13 10:35) [58]
> Ты должен исходить из того, что он может загадать любые
> в указанном интервале.

Любые разные или любые и одинаковые тоже?

Это существенно. Так как в одном случае таких пар нет, а в другом есть одна, которая и озвучена.

← →
Sha © (2013-07-17 10:57) [63]

Первое число - любое из диапазона 3..100.
Второе число - любое из диапазона 3..100.
Естественно, они могут совпасть)

← →
Визирь 3 (2013-07-17 11:03) [64]

ну, это не очевидно из фразы:

> Я загадал два числа от 3 до 100.

потому и уточнил. Дело в том. что я первоначально решал исходя из предположения, что одинаковые нельзя и получал, что решения нет. У вас же заметил, что вы используете и диагональ. Изменил и получил ответ. Проанализировав нашел и причину.

← →
Дмитрий СС (2013-07-17 11:09) [65]

> Sha © (17.07.13 10:44) [61]

В твоем варианте получается что оба числа простые и подобрать не так сложно.

Но в исходной задаче, если оба числа простые - то первый визирь сразу бы сказал что он может их назвать.

Поэтому такая переформулировка не эквивалентна исходной задаче.

← →
Sha © (2013-07-17 11:10) [66]

Понимаю.

Решая задачу, я предположил, что если бы одинаковые было нельзя,
фраза звучала как-то так: "Я загадал два различных числа от 3 до 100".

← →
Sha © (2013-07-17 11:11) [67]

> Дмитрий СС (17.07.13 11:09) [65]
> В твоем варианте получается что оба числа простые...

Поясни, как это получается?

← →
Дмитрий СС (2013-07-17 11:24) [68]

Первый визирь (произведение = 24) подумал и говорит:
- Я не знаю что это за числа (т.е. это может быть 3*8 и 6*4)

На что второй (имея сумму = 11) ответил:
- Я был в этом уверен (т.к. все комбинации 3*8, 4*7, 5*6 не раскладываются однозначно на множители от 3 до 100).
Если бы второй услышал сумму=10, но не был бы уверен (т.к. произведение мого бы быть 3*7 (два простых числа)).

Тогда первый говорит (поняв, что если второй уверен, то сумма равна 11):
- В таком случае, я знаю, что это за числа (3 и 8).

Второй:
- Тогда и я знаю, что это за числа (тут мне уже лень рассуждать, но думаю не сложно исключить 4и7 и 5и6).

← →
Визирь 3 (2013-07-17 11:26) [69]

4*7 - однозначно в нашем диапазоне

← →
Дмитрий СС (2013-07-17 11:28) [70]

4и7 и 5и6 исключаются потому, что первый бы сразу назвать эти числа. Вот.

← →
Визирь 3 (2013-07-17 11:28) [71]

У второго визиря в случае возможности одинаковы пар может быть

[13, 19, 25, 29, 31, 37, 43, 49, 53, 55]

в случае только различных

[13, 19, 25, 29, 31, 37, 43, 49, 53]

11 тут нет.

← →
Визирь 3 (2013-07-17 11:30) [72]

> 5и6

нет

5*6 = 10 * 3

← →
Дмитрий СС (2013-07-17 11:31) [73]

если бы были числа 4 и 7 . первый визирь имея произведение = 28 = 2 * 2 * 7 сразу бы ответил что знает эти числа, т.к. разложения 2 и 14 не может быть по условию задачи.

← →
Дмитрий СС (2013-07-17 11:33) [74]

с 4 и 7 определились, сейчас с 5 и 6 попробую

← →
Визирь 3 (2013-07-17 11:35) [75]

> Дмитрий СС (17.07.13 11:31) [73]

Все это более чем замечательно. Но никак не проливает свет на [61].

← →
Визирь 3 (2013-07-17 11:35) [76]

на 65, конечно.

> Дмитрий СС (17.07.13 11:24) [68]
> т.к. все комбинации 3*8, 4*7, 5*6 не раскладываются однозначно на множители от 3 до 100).

А как еще можно разложить 28=4*7=?*?

> Если бы второй услышал сумму=10, но не был бы уверен (т.к. произведение мого бы быть 3*7 (два простых числа)).

Не понял.

← →
Дмитрий СС (2013-07-17 12:01) [78]

← →
Дмитрий СС (2013-07-17 12:20) [79]

> > Если бы второй услышал сумму=10, но не был бы уверен (т.
> к. произведение мого бы быть 3*7 (два простых числа)).
>
> Не понял.

Если сумма может быть разложена на сумму двух простых чисел, то второй визирь уже не может быть уверен в том что первый не знает чисел.

> Дмитрий СС (17.07.13 12:20) [79]
> Если сумма может быть разложена на сумму двух простых чисел,
> то второй визирь уже не может быть уверен в том что первый не знает чисел.

Ну, это очевидно.
В этой задаче проще не пользоваться простотой чисел )

Гораздо выгоднее подсчитывать количество всевозможных произведений
чисел из заданного диапазона.

Это также позволит легко поиграть с границами при желании.

Типа пятничная задачка Найти похожие ветки