|
|
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Basil A. Sidorov, прошу прощения. Не читал. Про литературное. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 19:12 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
maytonBasil A. Sidorov, прошу прощения. Не читал. Про литературное.тех в таком стиле был написан кнутом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 19:20 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
mayton- это не исходник с каментами а текст с вкраплениями исходников.все гораздо проще. хаскель - сплошные дефенишины. слева имя, справа выражение. подсвечивать просто нечего. а Душкин, просто слишком уж превозносит этот хацкель. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 19:22 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Увы. Мне кроме Душкина было больше некого читать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 19:27 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 19:42 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
maytonBasil A. Sidorov, прошу прощения. Не читал. Про литературное.Пишем, напускаем препроцессор и получаем в одном файле исходный текст программы на паскале :), а в другом - документацию на программу. Второй файл предполагалось скармливать TeX-у :) P.S. Тех, кто собирается фыркать на "препроцессор", "два файла" и прочие детали реализации, сразу предупрежу, что "не на то дерево лаете". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 19:53 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
И не собирался я фыркать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 20:54 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Basil A. SidorovmaytonBasil A. Sidorov, прошу прощения. Не читал. Про литературное.Пишем, напускаем препроцессор и получаем в одном файле исходный текст программы на паскале :), а в другом - документацию на программу. Второй файл предполагалось скармливать TeX-у :) P.S. Тех, кто собирается фыркать на "препроцессор", "два файла" и прочие детали реализации, сразу предупрежу, что "не на то дерево лаете".Это Вы сейчас с кем разговариваете? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 21:23 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
maytonAndreTMНа самом деле, самое "сложное" - это проверка сократимости дробей. По сравнению с этим, все остальное (построение дробей, расположение их в неубывающем порядке) - требует намного меньше затрат ресурсов. Да. Я думал об этом. Если расположить дроби квадратной матрицей (там верхняя половина выше диагонали выходит) то часть дробей надо будет вычеркнуть из проверки. Если тупо в лоб , то мартица, для экономии памяти битовая. пройтись по номерам строк и столбцов, взвести в 1 пересечения где остаток от деления не равен 0 при наступании на диагональ перейти на следующую итерацию. Напечатать в виде дроби стороку и столбец матрицы со значением элемента равным 1. приблизительно так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 23:08 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Да. Я только хитрее думал. Уж коли мы всё равно сортируем и выводим в консоль неубывающую последовательность. То дубликаты такие как 1/2 и 2/4 при выводе будут идти рядышком как . 1/2 1/2 . И их можно дропать непосредственно перед выводом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 23:35 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
mayton, Дубликаты( сокращения 2/4 3/6 4/12 ) уйдут сами при проверке остатка от деления. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 23:42 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
ДохтаР, ок. Убедил. Значит создаём треугольную матрицу единиц. Потом в 1 проход проходим и сбрасываем в ноль все ячейки где x%y==0 А во второй проход?..... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2013, 23:46 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
mayton, В принципе можно сразу печатать дроби во вложенном цикле без матриц если остаток от деления не равен 0. когда сумма счтечиков циклов( внешнего и внутреннего) равна ширине матрицы перепрыгиваем на следующую итерацию( достигли диагонали). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 00:01 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Попробую нарисовать для N=6 Получается довольна запутано. И нет яркой последовательности внутри матрицы Код: sql 1. 2. 3. 4. 5. 6. 7. После фильтрации дубликатов Код: sql 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 00:12 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Яростный Мечесли я правильно понял идею 13851216 то сокращать дроби не придется, т.к. все одинаковые по значению будут найдены последовательно, и можно указать самую простую из них (с наименьшим знаменателем). тот алгоритм требует O(N) памяти на всё про всё и порядка O(N) времени на одну дробь (каждый раз поиск минимальной дроби по всем делителям).Почти. Код примерно такой: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. Но первый внутренний цикл - O(N), внешний - O(N 2 ) или несущественно лучше, суммарно O(N 3 ). Кроме того, решение слишком уж "лобовое". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 00:20 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
AbstractionЯростный Мечесли я правильно понял идею 13851216 то сокращать дроби не придется, т.к. все одинаковые по значению будут найдены последовательно, и можно указать самую простую из них (с наименьшим знаменателем). тот алгоритм требует O(N) памяти на всё про всё и порядка O(N) времени на одну дробь (каждый раз поиск минимальной дроби по всем делителям).Почти. Код примерно такой: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. Но первый внутренний цикл - O(N), внешний - O(N 2 ) или несущественно лучше, суммарно O(N 3 ). Кроме того, решение слишком уж "лобовое".можно полный код программы, хочу протестить производительность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 00:28 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Надо полагать GCD - это greatest common divisor. ( http://en.wikipedia.org/wiki/Euclidean_algorithm) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 00:36 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
maytonНадо полагать GCD - это greatest common divisor. ( http://en.wikipedia.org/wiki/Euclidean_algorithm)] http://en.wikipedia.org/wiki/Euclidean_algorithm) та я понял. просто предположил что существует полный исходник. не хотелось время тратить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 00:37 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Поиск сокращаемых дробей в матрице не дает мне покоя. Для случая с N=256 она будет выглядеть примерно так если считать ее черно-белой биткартой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 01:02 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
maytonПоиск сокращаемых дробей в матрице не дает мне покоя. Для случая с N=256 она будет выглядеть примерно так если считать ее черно-белой биткартой. ничего не понял. можешь пояснить картинку? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 01:08 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
maytonПопробую нарисовать для N=6 Получается довольна запутано. И нет яркой последовательности внутри матрицы Код: sql 1. 2. 3. 4. 5. 6. 7. После фильтрации дубликатов Код: sql 1. 2. 3. 4. 5. 6. 7. Лохонолся я с остатком от деления , не покрывает все варианты решения. Но но намек на GCD , натолкнул на мысть сделать наоброт. 2/3 = 2*2/3*2 =4/6 Тоже самое для 3/4=3*3/3*4=9/12 4/5=16/25 проходя по циклу от меньшего к большему путем умножения числителя и знаменателя на числитель в матрице отмечать фейковые дроби наперед. вирианты которые в последствии выводит не нужно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 01:11 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Ну вот самая плотная штрих-пунктирная прямая под углом 30 градусов к горизонту это пикселы с координатами (1,2),(2,4),(3,6)...(n,2*n). Я просто сделал матрицу более визуально наглядной. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 01:18 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
maytonНу вот самая плотная штрих-пунктирная прямая под углом 30 градусов к горизонту это пикселы с координатами (1,2),(2,4),(3,6)...(n,2*n). Я просто сделал матрицу более визуально наглядной. Они то как раз тебе и не нужны. Потому что это скращаемые дроби. Остаток от деления == 0 тебе покажет что это сокращаемая дробь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 01:32 |
|
||
|
Задачка с дробями.
|
|||
|---|---|---|---|
|
#18+
Да это и ежу понятно что не нужны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2013, 01:41 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=38131333&tid=1341932]: |
0ms |
get settings: |
10ms |
get forum list: |
24ms |
check forum access: |
5ms |
check topic access: |
5ms |
track hit: |
194ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
73ms |
get tp. blocked users: |
2ms |
| others: | 242ms |
| total: | 568ms |

| 0 / 0 |
