Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Гафаров Юлай, 15 августа 2018 г. 20:09:58
     Решил без алгоритма Евклида, аккуратным перебором всех делителей.
     19 строчек вычислений против 5 строчек у алгоритма Евклида. В качестве упражнения - почему бы и нет. В качестве рекомендуемого алгоритма - вряд ли.
  2  Михаил Владимирович Завялов, 28 февраля 2018 г. 23:50:47
     То чувство когда превысил лимит времени на простецкой задаче.
  3  Беляев Сергей Николаевич, 20 декабря 2015 г. 15:13:32
     
     Добавлены новые тесты. Все решения были перепроверены.
  4  Дмитрий Фадеев, 18 февраля 2012 г. 13:44:31
     Алгоритм Евклида
  5  Неизвестный, 17 декабря 2011 г. 13:39:44
     Не верно поставленно условие задачи. Говорится, что A, B <= 10^9, но а в отрицательную сторону где у них придел или он равен бесконечности??? Вот если-бы было сказано 0<=;A, B <= 10^9, тогда понятно, а так.....
     А текст "натуральные числа" ни о чем не говорит?
  6  Иванов Кирилл, 23 июля 2010 г. 9:17:05
     Ха, зачетное решение. С таким алгоритмом я и глазом моргнуть не успел там, где я своим ждал несколько секунд.
  7  Коншин Андрей Сергеевич, 21 декабря 2009 г. 23:10:32
     насчет алгоритма,я чуть позже понял......тот который в решении разобран,работает во много раз быстрее
     ну это уже давно всем известно, что алгоритм эвклида - лучший алгоритм поиска НОД.
  8  Коншин Андрей Сергеевич, 04 ноября 2009 г. 3:04:33
     Я почитал ваше решение.....((( Алгоритм евклида,насколько я знаю,выглядит по другому в высшей математике! И для усвоения он проще!
     Да не ужели. Это он самый и есть. В высшей математике он еще и с многочленами, вряд ли он проще. Я как человек с высшим математическим образованием вам говорю :)
  9  Sheveliukhin S. A., 24 марта 2009 г. 13:50:08
     Два раза "Time limit exceeded" получил, за свои варианты ответа на 7 тесте. Хотя оба варианта работоспособные. Вам следует сделать отдельно задачи: "НОД" и "НОД Методом Евклида", а не навязывать возможно единственно правильное решение Евклидом.
     Вы предлагаете сделать еще более простую задачу, для малых a и b? Вообще то ничего плохого нет в том, чтобы учить вычислять НОД Евклидом, т.к. это лучший алгоритм и его всегда практично использовать, в том числе и для малых a и b.
  10  Королёв Александр Максимович, 01 марта 2009 г. 15:14:05
     Почему неправильный ответ?
     Вам нужно либо условие поменять, либо типы переменных, т.к. значение a*b может оказаться за пределами типа longint.
  11  Ладик Артём, 10 ноября 2008 г. 21:10:25
     Советую строку "while a*b > 0 do" заменить на "while (a<>0) and (b<>0) do", а что если оба числа под 1000000000000??????? =]]]]]]
     А в моем алгоритмическом языке переменные не ограничены размером ;) Вообще то задача решается так с типом int64. Ну а те, кто ошибутся будут знать про ограничения лучше, так что пусть так как есть.
  12  Календо Дима, 28 сентября 2008 г. 15:36:29
     если вы сдавали код как в "решении" и использовали longint то у вас в 5 тесте переполнение в проверке a*b>0
     Однако замечу, что решение то верное, о типе на паскале там не сказано: если сдавать как int64 то вроде все Ок.
  13  Александров Александр Витальевич, 07 марта 2008 г. 21:37:17
     можете повторить теорему эвклида, а то я её не помню, а то что дано ниже тоже не понял
     Яндекс - найдется все. Напишите там "Алгоритм Евклида", наверняка найдете то, что ищите (возможно даже на этом сайте).
  14  Нагин Сергей Юриевич, 12 февраля 2008 г. 19:07:08
     лучшый тест 1 1000000000 только евклид пройдет!!!!!!!!!!!!!!!!!!!
     ну это да
  15  Князькин Ярослав Вячеславович, 26 декабря 2007 г. 17:32:19
     Почему превышает лимит времени?
     Ваш алгоритм поиска НОД неэффективен. Подумайте, как он работает на двух простых числах, близких к миллиарду.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru