Сообщений в теме: 101

[asr]

Тема для интересных задач.
Обсуждение решений и реализаций на разных языках, сравнение, нахождение лучшего.

Сообщение отредактировал asr: 22.08.2012, 12:32:47

[asr]

Проверьте, как работает ваша функция на разных парах чисел. Например, чему равен НОД (1071, 462)?

*Программисты, не подсказывать! Задача предлагается только для Натальюшки (точнее говоря, для ее сына, который хочет стать программистом).

Поскольку Натальюшка назвала меня ненастоящим программистом.... )

Результат равен 21 ))
Простым перебором (Oracle):


FUNCTION NOD
( vliP1 IN number,
vliP2 IN number)
RETURN number IS
vliI number;
vliRes number;
BEGIN
vliRes := 0;
for vliI in 1..LEAST(vliP1,vliP2) loop
if (Round(vliP1/vliI)=vliP1/vliI) and (Round(vliP2/vliI)=vliP2/vliI) then
vliRes := vliI;
end if;
end loop;
RETURN vliRes;
END;

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

Сообщение отредактировал asr: 21.08.2012, 10:06:27

[asr]

Проверьте, как работает ваша функция на разных парах чисел. Например, чему равен НОД (1071, 462)?

*Программисты, не подсказывать! Задача предлагается только для Натальюшки (точнее говоря, для ее сына, который хочет стать программистом).

Поскольку Натальюшка назвала меня ненастоящим программистом.... )

Результат равен 21 ))
Простым перебором (Oracle):


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

Если нужно сделать кучу быстрых операций.
В качестве варианта если ввести таблицу простых чисел, найти делитель из простых для первого числа, делитель из простых для второго.
"Пересечение" (умножение или равно) даст шаг перебора. Недостатком буде ограничение по длине обрабатываемых чисел (по длине таблицы простых чисел).

Сообщение отредактировал asr: 21.08.2012, 14:50:33

[Visual1]

Так напишите просто, пожалуйста, список тех программ которые нужно знать.

Для решения задачи нахождения НОД можно не знать вообще никаких программ. Как правильно выше заметил Квазимодо, для решения данной задачи даже не обязательно знать ЯП (языки программирования). Ведь решение надо начинать не с команд и инструкций ЯП, а с продумывания пошаговых действий. Что будем делать на первом шаге, какой получим результат, что будем с ним делать? Какая будет дальнейшая последовательность действий? Иначе говоря, сначала нужен алгоритм решения. Нашли алгоритм, который работает без ошибок? Поздравляю, это уже хоть какое-то - возможно, неэффективное - но все же, решение задачи. Реализация алгоритма на одном из ЯП нужна только в случае, если нужна программа, работающая на реальном устройстве.

Вот asr предложил (и реализовал в среде Oracle) алгоритм, в котором все действия состоят в простом последовательном переборе чисел. Он даже получил правильный результат, НОД(1071, 462) = 21. Но какой ценой получен этот результат? Сколько сотен чисел "тупо в лоб" пришлось для этого перебрать? А если исходные числа будут не 1071 и 462, а миллионы? Миллиарды? Как поведет себя такой алгоритм на устройстве с малым объемом памяти и маломощным процессором (например, недорогой сотовый телефон)?

Для непрограммиста такой "алгоритм" с большой натяжкой еще можно как-то допустить. (Однако, интересные какие пошли "непрограммисты". Они умеют кодить в среде Oracle! ). Но вот программиста за такое надо гнать поганой метлой с работы. Ведь такие простые учебные задачи не сегодня и не вчера появились. Они давно известны, поэтому должны быть известны и алгоритмы их решения. Программист обязан их знать. А новичок, начинающий программист, должен уметь их найти и правильно применить (реализовать на ЯП).

Сообщение отредактировал Visual1: 21.08.2012, 19:20:18

[asr]

Вот asr предложил (и реализовал в среде Oracle) алгоритм, в котором все действия состоят в простом последовательном переборе чисел. Он даже получил правильный результат, НОД(1071, 462) = 21. Но какой ценой получен этот результат? Сколько сотен чисел "тупо в лоб" пришлось для этого перебрать? А если исходные числа будут не 1071 и 462, а миллионы? Миллиарды? Как поведет себя такой алгоритм на устройстве с малым объемом памяти и маломощным процессором (например, недорогой сотовый телефон)?

Сколько перебрал? 462!
Очень интересны доп.постановки после основной.
Привязки к устройству с малым обьемом памяти не было.
Постановка изначально стояла "возмите любой язык"

Готов выслушать АРГУМЕНТИРОВАНЫЕ замечания.
А не бла-бла-бла.... если бы да ка бы... а если бы у бабушки был....

Сообщение отредактировал asr: 21.08.2012, 21:21:28

[Visual1]

Сколько перебрал? 462!

Многовато что-то. Хотя вы же сами отнесли себя к не программистам, в таком случае для вас это нормально.
А вообще, для данной пары чисел (1071, 462) результат (21) при правильно выбранном алгоритме вычисляется всего за 3 (три!) итерации.

Очень интересны доп.постановки после основной.
Привязки к устройству с малым обьемом памяти не было.

Не было и привязки к устройству с большим объемом памяти. Не было привязки вообще ни к какому устройству (настольный компьютер РС или Мас, сотовый телефон и т.д.). Ну и что, это значит, уже нельзя обсуждать границы применимости предложенного Вами алгоритма?

Постановка изначально стояла "возмите любой язык"

Так ведь у меня и нет претензий к вашему выбору.

Готов выслушать АРГУМЕНТИРОВАНЫЕ замечания.
А не бла-бла-бла.... если бы да ка бы... а если бы у бабушки был....

Напрасно так болезненно реагируете. Я не хотел Вас обидеть. Напротив, я рад видеть Ваш интерес к предложенной задаче. Вы пока единственный человек, кто дал правильное (хотя и крайне неэффективное) решение. Но согласитесь, для профессионального программиста такое решение - просто позор. (Напоминаю еще раз, я просил программистов не отвечать. Эта задачка предлагалась для школьников старших классов, желающих стать программистами.)

[asr]

уже нельзя обсуждать границы применимости предложенного Вами алгоритма?

Реализовано на оракл. Как понимаете это нельзя запустить на любом маке, андроиде или настолном компе. ИЗНАЧАЛЬНО.
Обсуждение границ применимости сводится к одному. Применимо только на сервере БД там где крутится сотни тысяч/миллионы записей, тысячи запросов в секунду. ХЗ о каком ограничении по обьему памяти вы ведете речь.

для профессионального программиста такое решение - просто позор

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

[Visual1]

для профессионального программиста такое решение - просто позор

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

"Разово сосчитать"? Напоминаю, по условию было - написать функцию. Известно ли Вам, для чего в программах нужны функции?

[vladimir55]

Да что же ты будешь делать?!!! В последнее время тут что не тема, так повод помериться членами. Что за любовь такая унижать друг друга? И самое интересное: в темах сплошной офтоп. Например, тут спрашивали про то, где можно получить образование, а про что сейчас ведется разговор? Про то, кто круче разбирается в алгоритмах? Не так давно была тема жалоба на злобных юзеров. Чем там дело закончилось? Выяснением вопроса "а кого вообще считать программером?". Господа программеры, делаю предложение: создайте себе отдельную тему и кичитесь там своими регалиями, а в другие, если по теме сказать нечего, просто не суйтесь. Открыли, прочитали, повозмущались про себя, досчитали до 10, глубоко вдохнули-выдохнули и закрыли.

[asr]

для профессионального программиста такое решение - просто позор

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

"Разово сосчитать"? Напоминаю, по условию было - написать функцию. Известно ли Вам, для чего в программах нужны функции?

И?? Почему нельзя разово сосчитать функцией? Можно разово сосчитать и процедурой. А можно вообще обойтись скриптом.
В чем вопрос? В том что вы фунции используете только в программах и нигде более? Так это ваши трудности.
Хотелось бы увидеть ваш алгоритм.

vladimir55 скинул мне алгоритм в 12 операций для чисел 1071, 462. Давайте свой в "3 (три!) итерации".

А еще лучше чуток подправим задание, чтобы не пользоваться теми решениями которые в инете.
Скажем так: наибольший делитель, когда первое число будет иметь дробную часть x.18 а второе число дробную часть x.67

Жду прорыва математического гения.

Сообщение отредактировал asr: 22.08.2012, 09:23:51

[topcraze]

Давайте свой в "3 (три!) итерации

Дано а, b, a>b
Нужно - НОД

1) x = а-b
2) if (x ==0) end; else a=x, goto 1

поправьте, если что не так, последний раз Евклида реализовывала лет 7 назад,в реальной жизни пользуюсь готовыми реализациями

Сообщение отредактировал topcraze: 22.08.2012, 09:44:06

[asr]

Давайте свой в "3 (три!) итерации

Дано а, b, a>b
Нужно - НОД

1) x = а-b
2) if (x ==0) end; else a=x, goto 1

поправьте, если что не так, последний раз Евклида реализовывала лет 7 назад

1) x = mod(а-b)

А теперь усложняем задачу, чтобы не пользоваться теми решениями которые в инете.
Скажем так: наибольший делитель, когда первое число будет иметь дробную часть x.18 а второе число дробную часть x.67

Сообщение отредактировал asr: 22.08.2012, 10:01:29

[Visual1]

Хотелось бы увидеть ваш алгоритм.

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

vladimir55 скинул мне алгоритм в 12 операций для чисел 1071, 462. Давайте свой в "3 (три!) итерации".

Вас в гугле забанили? Потрудитесь сами хоть немного.

[topcraze]

asr, НОД по определению вычисляется для целых чисел..
и это.. алгоритм Евклида и в школе рассказывают и в универе, так что запоминается напрочь и инет не нужен для того, чтобы вспомнить

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

Сообщение отредактировал topcraze: 22.08.2012, 10:19:34

[asr]

Хотелось бы увидеть ваш алгоритм.

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

vladimir55 скинул мне алгоритм в 12 операций для чисел 1071, 462. Давайте свой в "3 (три!) итерации".

Вас в гугле забанили? Потрудитесь сами хоть немного.

Да нет, не забанили, я даже увидел что вы не смогли свои примеры нарисовать. Фантазии видимо не хватило.
Опять бла-бла-бла.....

[asr]

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

А без гугла слабо?
А если решения нет в гугле у вас это будет нерешаемая проблема?

Сообщение отредактировал asr: 22.08.2012, 10:49:38

[Visual1]

Да нет, не забанили, я даже увидел что вы не смогли свои примеры нарисовать. Фантазии видимо не хватило.
Опять бла-бла-бла.....

Какие я вам должен примеры "нарисовать"? Я дал задачу из школьного курса, чтобы пользователь Натальюшка могла проверить способности к программированию своего сыночка. Я просил программистов не подсказывать. Однако вы решили дать ваше решение. Что ж, если вы не программист, то вы с задачей справились удовлетворительно, как я уже говорил. А если вы программист, то вы с предложенной задачей не справились.
Дальнейшие попытки решения вы прекратили. Вместо этого от вас только ненужные бла-бла-бла.
В таком случае, я не вижу смысла дальше тратить на вас свое время.
До свидания.

[asr]

Да нет, не забанили, я даже увидел что вы не смогли свои примеры нарисовать. Фантазии видимо не хватило.
Опять бла-бла-бла.....

Какие я вам должен примеры "нарисовать"? Я дал задачу из школьного курса, чтобы пользователь Натальюшка могла проверить способности к программированию своего сыночка. Я просил программистов не подсказывать. Однако вы решили дать ваше решение. Что ж, если вы не программист, то вы с задачей справились удовлетворительно, как я уже говорил. А если вы программист, то вы с предложенной задачей не справились.
Дальнейшие попытки решения вы прекратили. Вместо этого от вас только ненужные бла-бла-бла.
В таком случае, я не вижу смысла дальше тратить на вас свое время.
До свидания.

Конечно не тратьте свое бла-бла-бла... на сотрясание воздуха...

[topcraze]

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

А без гугла слабо?
А если решения нет в гугле у вас это будет нерешаемая проблема?

вот именно этот момент - распространяется ли понятие НОД на дробные числа - да вспомнить слабо, потому как это информация для меня ценности в текущий момент времени не представляет
нет решения в гугле - это моя обычная рабочая ситуация вот именно сейчас есть задача, решения который в гугле нет, она для меня значительно более приоритетная, чем представленная тут, так что...
но вы можете тоже списать на "слабо", мне не жалко

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

[asr]

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

А без гугла слабо?
А если решения нет в гугле у вас это будет нерешаемая проблема?

вот именно этот момент - распространяется ли понятие НОД на дробные числа - да вспомнить слабо, потому как это информация для меня ценности в текущий момент времени не представляет
нет решения в гугле - это моя обычная рабочая ситуация вот именно сейчас есть задача, решения который в гугле нет, она для меня значительно более приоритетная, чем представленная тут, так что...
но вы можете тоже списать на "слабо", мне не жалко

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

На решение вышепоставленной задачи методом "тупого" перебора у меня ушло 2 мин без использования гугл. Запрос отработал 0,00 сек более точно оракл не показал.
Поскольку используется "тупой" перебор, я использовал то что наиболее мощное в моем распоряжении: оракл БД.
Т.е. оценка задачи-выбор-языка-реализация-результат на все ушло 3-4 минуты.

"распространяется ли понятие НОД на дробные числа - да вспомнить слабо" мне тоже слабо (тем более я этого и не знал видимо те уроки я прогулял), но мне не слабо это проверить.
Вам трудно выделить 5 минут?

Сообщение отредактировал asr: 22.08.2012, 11:43:44

[topcraze]

1) Перебор с дробями работает?
2) реализация поиска НОДа для дробных чисел так как она мне в общем представляется сейчас займет более 5 минут и самое главное - мне это сейчас не нужно!
3) модератор поощряет оффтоп?