Здравствуйте всем! У меня возникла проблема, нужно найти все натуральные числа А,В и С в интервале от 1 до 200, для которых будет исполняться равенство А*В=В+С. Как его более рационально решить, подскажите пожалуйста.
Василий_Решетняк
6.12.2010 4:22
Извините, уже сам додумался. Оказалось совсем легко. Вот код
var a,b,c:integer; begin for a:=1 to 200 do begin for b:=1 to 200 do begin for c:=1 to 200 do begin if a*b=b+c then writeln('a=',a,'b=',b,'c=',c); end; end; end; readln; end.
TarasBer
6.12.2010 14:28
А препод возьмёт, и скажет: "Хорошо, молодой человек, а теперь решите мне ту же задачу не для 200, а для 2000."
Lapp
6.12.2010 14:46
Цитата(Василий_Решетняк @ 5.12.2010 23:23)
Как его более рационально решить, подскажите пожалуйста.
Если ты действительно хотел более рациональное решение, то есть пара замечаний. Во-первых, зачем столько begin/end? одиночные оператоы совершенно необязательно заключать в операторные скобки. Во-вторых, число 200 надо задавать константой (ниже увидишь, почему). В третьих, преобразуем то выражение к такому вот виду:
A = 1 + C/B
Отсюда делаем несколько выводов. 1. Поскольку C/B>0, то A>1. Это значит, что цикл по A можно начинать с 2. 2. C/B должно быть целым, так что C кратно B. Это значит, что внутренний цикл можно вести с шагом B (переделав его с for на while).
Все это понижает общее число проверок с 8 000 000 (восемь миллионов) до 218 502, то есть в 36 раз. При увеличении диапазона с 200 до 300 выигрыш доходит до 51 раза, а если увеличить диапазон до 1000, то выиграем в 141 раз.
Вот прога, которой я пользовался:
const d=200; var a,b,c: integer; m,n: LongInt; begin for a:=2 to d do for b:=1 to d do begin c:=b; while c<=d do begin if a*b=b+c then begin writeln('a=',a,' b=',b,' c=',c); Inc(n) end; Inc(c,b); Inc(m) end end; WriteLn('N=',n,' M=',m); readln end.
Тут вставлены также подсчеты числа найденных решений и общего количества итераций.
P.S. Я уж не говорю, что имеет смысл все же отделять вывод чисел пробелами, а не лепить друг к другу..
Добавлено через 4 мин. Собственно, это не предел оптимизации )). Следующим шагом будет замена тупых циклов на умное деление )).
TarasBer
6.12.2010 14:54
Lapp, я не только про скорость. Вот примени алгоритм для 2000.
Lapp
6.12.2010 15:02
Цитата(TarasBer @ 6.12.2010 10:54)
Lapp, я не только про скорость. Вот примени алгоритм для 2000.
Тарас, я понимаю, о чем ты, мне для этого не надо применять )). Почему ты думаешь, что я возражаю? )) У тебя очень дельный совет. Я его не видел до отсылки моего ответа. Хотя, конечно, если в условии дано 200, то можно ограничиться типом integer. А со стороны препа будет не совсем корректно менять на 2000. Этак можно и вовсе уехать на 20000000000000000 или больше )).
andriano
16.12.2010 3:51
Объясните мне, зачем цикл по А? А нужно просто вычислять.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.