ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка с дробями.
25 сообщений из 131, страница 1 из 6
  1  все
Задачка с дробями.
    #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:31
| Ответить | Цитировать | Написать  
Задачка с дробями.
    #38130664
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
Забыл дописать "БЫСТРО!"
...
Рейтинг: 0 / 0
30.01.2013, 14:36
| Ответить | Цитировать | Написать  
Задачка с дробями.
    #38130741
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
Дроби также должны быть несократимыми, судя по примеру? O(N 2 ) понятно как (хранить массив "следующих" числителей и на каждом шаге находить соответствующий минимальной дроби и увеличивать его), но, кажется, можно быстрее.
...
Рейтинг: 0 / 0
30.01.2013, 15:01
| Ответить | Цитировать | Написать  
Задачка с дробями.
    #38130744
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да. Дробь 2/4 выпадает из списка т.к. это суть 1/2.
...
Рейтинг: 0 / 0
30.01.2013, 15:03
| Ответить | Цитировать | Написать  
Задачка с дробями.
    #38130749
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
wadmanЗабыл дописать "БЫСТРО!"
Это олимпиадная. Но в данном форуме мы можем медитировать над ней
достаточно долго. :)
...
Рейтинг: 0 / 0
30.01.2013, 15:04
| Ответить | Цитировать | Написать  
Задачка с дробями.
    #38130754
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
mayton,

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

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

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

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


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