Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка с дробями. / 25 сообщений из 131, страница 1 из 6
  1  все
30.01.2013, 14:31
    #38130653
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Дано N (натуральное). Вывести список рациональных дробей
в неубывающем порядке где числитель и знаменатель - целые от 1 до N.
И числитель не больше знаменателя (т.е. результат дроби меньше 1.0)

Вход:
5
Выход:
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 14:36
    #38130664
wadman
wadman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Забыл дописать "БЫСТРО!"
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 15:01
    #38130741
Abstraction
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Дроби также должны быть несократимыми, судя по примеру? O(N 2 ) понятно как (хранить массив "следующих" числителей и на каждом шаге находить соответствующий минимальной дроби и увеличивать его), но, кажется, можно быстрее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 15:03
    #38130744
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Да. Дробь 2/4 выпадает из списка т.к. это суть 1/2.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 15:04
    #38130749
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
wadmanЗабыл дописать "БЫСТРО!"
Это олимпиадная. Но в данном форуме мы можем медитировать над ней
достаточно долго. :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 15:06
    #38130754
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
mayton,

какие ограничения на память и скорость?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 15:11
    #38130767
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
По учебнику N<=255. Но я решил снять ограничение для этого форума.
По остальному - задачки писались для учебника в TurboPascal 7.0.
Память и всё остальное - соотвественно можете выбрать исходя
из этих сведений.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 16:13
    #38130921
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
На самом деле, самое "сложное" - это проверка сократимости дробей. По сравнению с этим, все остальное (построение дробей, расположение их в неубывающем порядке) - требует намного меньше затрат ресурсов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 16:19
    #38130935
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
AndreTMНа самом деле, самое "сложное" - это проверка сократимости дробей. По сравнению с этим, все остальное (построение дробей, расположение их в неубывающем порядке) - требует намного меньше затрат ресурсов.
Да. Я думал об этом. Если расположить дроби
квадратной матрицей (там верхняя половина выше диагонали выходит)
то часть дробей надо будет вычеркнуть из проверки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 16:33
    #38130961
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Я подумал так - строим матрицу разложения чисел на простые множители (даже необязательно вычислять степень сомножителя, достаточно признака того, что существует хотя бы один такой в числе), по ней легко затем находятся несократимые пары. Затем перебираем показатели числитель/знаменатель в порядке возрастания величины дроби, при этом выводя только несократимые.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 17:33
    #38131090
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Я тоже думал о разложении. Но недавно мне подсказали что для решения данной задачи
(сокращение дроби) достаточно алгоритма Евклида для расчета НОД.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 17:42
    #38131123
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
если я правильно понял идею 13851216
то сокращать дроби не придется, т.к. все одинаковые по значению будут найдены последовательно, и можно указать самую простую из них (с наименьшим знаменателем).
тот алгоритм требует O(N) памяти на всё про всё и порядка O(N) времени на одну дробь (каждый раз поиск минимальной дроби по всем делителям).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 17:55
    #38131156
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
maytonЯ тоже думал о разложении. Но недавно мне подсказали что для решения данной задачи
(сокращение дроби) достаточно алгоритма Евклида для расчета НОД.угу.. кмк, если для двух чисел - числителя и знаменателя, существует даже не НОД, а просто общий делитель, то эту дробь надо выкидывать из списка результатов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 17:58
    #38131162
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
S.G.maytonЯ тоже думал о разложении. Но недавно мне подсказали что для решения данной задачи
(сокращение дроби) достаточно алгоритма Евклида для расчета НОД.угу.. кмк, если для двух чисел - числителя и знаменателя, существует даже не НОД, а просто общий делитель, то эту дробь надо выкидывать из списка результатов.
Это смотря как обходить. Я искал решение класса "конечный автомат". Чтобы обходя
матрицу дробей выводит их в неубывающем порядке. Тоесть без доп. массивов
и сорт. структур. Но пока чет не вышло.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:17
    #38131190
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
maytonДано N (натуральное). Вывести список рациональных дробей
в неубывающем порядке где числитель и знаменатель - целые от 1 до N.
И числитель не больше знаменателя (т.е. результат дроби меньше 1.0)

Вход:
5
Выход:
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5о. тут ленивые вычисления помогут.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:25
    #38131200
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
maytonТоесть без доп. массивов
и сорт. структур.где ты это написал?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:27
    #38131203
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
ZyK_BotaNmaytonТоесть без доп. массивов
и сорт. структур.где ты это написал?
Зачем я буду ограничивать полёт чужой мысли? Я привел постановку олимпиадной задачи. Как есть.
А то что я искал это - отдельная тема. Можно искать а можно и забить. Но "ленивое решение"
мне еще интреснее будет. Жду...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:37
    #38131219
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
import Data.Ratio

main = putStr (show result)

result = foldl merge [] (rows 5)

rats n k = map ((%) k) [n, n-1..k+1]

rows n = map (rats n) [1..n]

merge [] s2 = s2
merge s1 [] = s1
merge (s1:s1s) (s2:s2s) 
    | s1 < s2   = s1 : (merge s1s      (s2:s2s))
    | s1 > s2   = s2 : (merge (s1:s1s) s2s)
    | otherwise = s1 : (merge s1s      s2s)


почему на форуме нету хацкельного тега срц? (
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:40
    #38131223
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
maytonЖду... done.

макс необходимая использумая паять(из-за сборщика) = паять под текущий результат + память под n чисел(т.е. для каждого числителя от 1-го до n). благодаря ленивости, под все знаменатели память выделять не нужно(достаточно по одному для каждого числителя).

т.е. используемая память - 2*n*sizeof(Rational)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:41
    #38131225
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
ZyK_BotaN, а в каком виде выводит? Просто из-за отсутствия форматирования со слешом типа "%i/%i" непонятно.
И что делает пакет Data.Ratio ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:45
    #38131231
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
maytonZyK_BotaN, а в каком виде выводит? Просто из-за отсутствия форматирования со слешом типа "%i/%i" непонятно.
И что делает пакет Data.Ratio ?тип данных - рациональные числа. с лева от % - числитель, справа знаменатель.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:52
    #38131241
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
Про [ src=haskel ] я подниму вопрос в модераторском форуме.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 18:57
    #38131254
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
maytonПро [ src=haskel ] я подниму вопрос в модераторском форуме.я пошутил.
в хаскеле нечего подсвечивать.
там кроме ключевых слов "modul, import, let, where, do" - нечего подсвечивать.

исходник хаскеля с подсветкой синтаксиса - не отличается от обычного текста ))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 19:02
    #38131262
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
А я вспомнил. Я читал эту тему у Душкина. Но меня особо поразило что
Хаскель исходник - это не исходник с каментами а текст с вкраплениями
исходников. Это конечно другим ЯП не дано.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2013, 19:08
    #38131275
Basil A. Sidorov
Basil A. Sidorov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка с дробями.
maytonЭто конечно другим ЯП не дано.Что значит "не дано"?
Литературное программирование Дональд Кнут для чего делал?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка с дробями. / 25 сообщений из 131, страница 1 из 6
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 509ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1341932]:
 0ms
get settings:
 8ms
get forum list:
 18ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 158ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 88ms
get tp. blocked users:
 2ms
others: 216ms
total:  509ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]