IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Найти числа удовлетворяющие равенство
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 2
Пол: Мужской
Реальное имя: Василий

Репутация: -  0  +


Здравствуйте всем! У меня возникла проблема, нужно найти все натуральные числа А,В и С в интервале от 1 до 200, для которых будет исполняться равенство А*В=В+С.
Как его более рационально решить, подскажите пожалуйста.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2





Группа: Пользователи
Сообщений: 2
Пол: Мужской
Реальное имя: Василий

Репутация: -  0  +


Извините, уже сам додумался. Оказалось совсем легко. Вот код
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.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


А препод возьмёт, и скажет:
"Хорошо, молодой человек, а теперь решите мне ту же задачу не для 200, а для 2000."


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Василий_Решетняк @ 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 мин.
Собственно, это не предел оптимизации )). Следующим шагом будет замена тупых циклов на умное деление )).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Lapp, я не только про скорость.
Вот примени алгоритм для 2000.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(TarasBer @ 6.12.2010 10:54) *
Lapp, я не только про скорость.
Вот примени алгоритм для 2000.

Тарас, я понимаю, о чем ты, мне для этого не надо применять )).
Почему ты думаешь, что я возражаю? )) У тебя очень дельный совет. Я его не видел до отсылки моего ответа.
Хотя, конечно, если в условии дано 200, то можно ограничиться типом integer. А со стороны препа будет не совсем корректно менять на 2000. Этак можно и вовсе уехать на 20000000000000000 или больше )).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Объясните мне, зачем цикл по А?
А нужно просто вычислять.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 1.12.2020 21:31
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name