powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка с дробями.
25 сообщений из 131, страница 2 из 6
Задачка с дробями.
    #38131280
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. Sidorov, прошу прощения. Не читал. Про литературное.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131299
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonBasil A. Sidorov, прошу прощения. Не читал. Про литературное.тех в таком стиле был написан кнутом.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131300
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton- это не исходник с каментами а текст с вкраплениями
исходников.все гораздо проще.

хаскель - сплошные дефенишины.

слева имя, справа выражение. подсвечивать просто нечего.
а Душкин, просто слишком уж превозносит этот хацкель.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131305
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Увы. Мне кроме Душкина было больше некого читать.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131320
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
public static IEnumerable<Tuple<int, int>> M(int n)
        {
            Func<int, int, int> gcp = (a, b) => 
            {
                while (b != 0)
                    b = a % (a = b);
                return a;
            };
            Func<int, int, Tuple<int, int>> f = (s1, s2) =>
                {
                    var t = gcp(s1, s2);
                    return Tuple.Create(s1 / t, s2 / t);
                };
            
            var src = Enumerable.Range(1, n);
            var res = (from s1 in src
                       from s2 in src
                       where s2 > s1
                       select f(s1, s2))
                      .Distinct();
            return res;
        }
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131333
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonBasil A. Sidorov, прошу прощения. Не читал. Про литературное.Пишем, напускаем препроцессор и получаем в одном файле исходный текст программы на паскале :), а в другом - документацию на программу. Второй файл предполагалось скармливать TeX-у :)

P.S. Тех, кто собирается фыркать на "препроцессор", "два файла" и прочие детали реализации, сразу предупрежу, что "не на то дерево лаете".
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131390
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И не собирался я фыркать.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131413
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovmaytonBasil A. Sidorov, прошу прощения. Не читал. Про литературное.Пишем, напускаем препроцессор и получаем в одном файле исходный текст программы на паскале :), а в другом - документацию на программу. Второй файл предполагалось скармливать TeX-у :)

P.S. Тех, кто собирается фыркать на "препроцессор", "два файла" и прочие детали реализации, сразу предупрежу, что "не на то дерево лаете".Это Вы сейчас с кем разговариваете?
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131498
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonAndreTMНа самом деле, самое "сложное" - это проверка сократимости дробей. По сравнению с этим, все остальное (построение дробей, расположение их в неубывающем порядке) - требует намного меньше затрат ресурсов.
Да. Я думал об этом. Если расположить дроби
квадратной матрицей (там верхняя половина выше диагонали выходит)
то часть дробей надо будет вычеркнуть из проверки.

Если тупо в лоб ,
то мартица, для экономии памяти битовая.
пройтись по номерам строк и столбцов, взвести в 1 пересечения
где остаток от деления не равен 0 при наступании на диагональ перейти на следующую итерацию.
Напечатать в виде дроби стороку и столбец матрицы со значением элемента равным 1.
приблизительно так.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131540
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да. Я только хитрее думал. Уж коли мы всё равно сортируем и выводим в консоль
неубывающую последовательность. То дубликаты такие как 1/2 и 2/4 при выводе
будут идти рядышком как

.
1/2
1/2
.

И их можно дропать непосредственно перед выводом.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131546
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Дубликаты( сокращения 2/4 3/6 4/12 ) уйдут сами при проверке остатка от деления.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131553
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ДохтаР, ок. Убедил. Значит создаём треугольную матрицу единиц. Потом
в 1 проход проходим и сбрасываем в ноль все ячейки где x%y==0

А во второй проход?.....
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131568
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,


В принципе можно сразу печатать дроби во вложенном цикле без матриц
если остаток от деления не равен 0.
когда сумма счтечиков циклов( внешнего и внутреннего) равна ширине матрицы
перепрыгиваем на следующую итерацию( достигли диагонали).
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131573
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Попробую нарисовать для N=6

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

Код: sql
1.
2.
3.
4.
5.
6.
7.
   1    2    3    4    5    6
1     1/2  1/3  1/4  1/5  1/6
2          2/3  2/4  2/5  2/6
3               3/4  3/5  3/6
4                    4/5  4/6
5                         5/6
6



После фильтрации дубликатов
Код: sql
1.
2.
3.
4.
5.
6.
7.
   1    2    3    4    5    6
1     1/2  1/3  1/4  1/5  1/6
2          2/3  ---  2/5  ---
3               3/4  3/5  ---
4                    4/5  ---
5                         5/6
6
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131579
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Яростный Мечесли я правильно понял идею 13851216
то сокращать дроби не придется, т.к. все одинаковые по значению будут найдены последовательно, и можно указать самую простую из них (с наименьшим знаменателем).
тот алгоритм требует O(N) памяти на всё про всё и порядка O(N) времени на одну дробь (каждый раз поиск минимальной дроби по всем делителям).Почти. Код примерно такой:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
int *numerators = new int[N];
for(int i=0; i<N; ++i) numerators[i] = 1;

while(true){
  int min = 0;
  for(int i=0; i<N; ++i){
    if(numerators[i]*(min+1) < numerators[min]*(i+1)) min = i;
  }
  if(numerators[min] == (min+1)) break;

  std::cout << numerators[min] << '/' << (min+1) << std::endl;

  while(GCD(numerators[min], min+1)!=1 && numerators[min]!=(min+1)) ++numerators[min];
}

delete[] numerators;

Но первый внутренний цикл - O(N), внешний - O(N 2 ) или несущественно лучше, суммарно O(N 3 ). Кроме того, решение слишком уж "лобовое".
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131581
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AbstractionЯростный Мечесли я правильно понял идею 13851216
то сокращать дроби не придется, т.к. все одинаковые по значению будут найдены последовательно, и можно указать самую простую из них (с наименьшим знаменателем).
тот алгоритм требует O(N) памяти на всё про всё и порядка O(N) времени на одну дробь (каждый раз поиск минимальной дроби по всем делителям).Почти. Код примерно такой:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
int *numerators = new int[N];
for(int i=0; i<N; ++i) numerators[i] = 1;

while(true){
  int min = 0;
  for(int i=0; i<N; ++i){
    if(numerators[i]*(min+1) < numerators[min]*(i+1)) min = i;
  }
  if(numerators[min] == (min+1)) break;

  std::cout << numerators[min] << '/' << (min+1) << std::endl;

  while(GCD(numerators[min], min+1)!=1 && numerators[min]!=(min+1)) ++numerators[min];
}

delete[] numerators;


Но первый внутренний цикл - O(N), внешний - O(N 2 ) или несущественно лучше, суммарно O(N 3 ). Кроме того, решение слишком уж "лобовое".можно полный код программы, хочу протестить производительность.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131586
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Надо полагать GCD - это greatest common divisor.

( http://en.wikipedia.org/wiki/Euclidean_algorithm)
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131587
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНадо полагать GCD - это greatest common divisor.

( http://en.wikipedia.org/wiki/Euclidean_algorithm)] http://en.wikipedia.org/wiki/Euclidean_algorithm) та я понял. просто предположил что существует полный исходник. не хотелось время тратить.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131594
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Поиск сокращаемых дробей в матрице не дает мне покоя. Для случая с N=256
она будет выглядеть примерно так если считать ее черно-белой биткартой.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131601
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПоиск сокращаемых дробей в матрице не дает мне покоя. Для случая с N=256
она будет выглядеть примерно так если считать ее черно-белой биткартой.

ничего не понял. можешь пояснить картинку?
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131602
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПопробую нарисовать для N=6

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

Код: sql
1.
2.
3.
4.
5.
6.
7.
   1    2    3    4    5    6
1     1/2  1/3  1/4  1/5  1/6
2          2/3  2/4  2/5  2/6
3               3/4  3/5  3/6
4                    4/5  4/6
5                         5/6
6



После фильтрации дубликатов
Код: sql
1.
2.
3.
4.
5.
6.
7.
   1    2    3    4    5    6
1     1/2  1/3  1/4  1/5  1/6
2          2/3  ---  2/5  ---
3               3/4  3/5  ---
4                    4/5  ---
5                         5/6
6



Лохонолся я с остатком от деления , не покрывает все варианты решения.
Но но намек на GCD , натолкнул на мысть сделать наоброт.
2/3 = 2*2/3*2 =4/6
Тоже самое для
3/4=3*3/3*4=9/12
4/5=16/25

проходя по циклу от меньшего к большему путем умножения числителя и знаменателя
на числитель в матрице отмечать фейковые дроби наперед.
вирианты которые в последствии выводит не нужно.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131605
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну вот самая плотная штрих-пунктирная прямая под углом 30 градусов
к горизонту это пикселы с координатами (1,2),(2,4),(3,6)...(n,2*n).
Я просто сделал матрицу более визуально наглядной.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131612
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНу вот самая плотная штрих-пунктирная прямая под углом 30 градусов
к горизонту это пикселы с координатами (1,2),(2,4),(3,6)...(n,2*n).
Я просто сделал матрицу более визуально наглядной.

Они то как раз тебе и не нужны.
Потому что это скращаемые дроби.
Остаток от деления == 0 тебе покажет что это сокращаемая дробь.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38131614
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да это и ежу понятно что не нужны.
...
Рейтинг: 0 / 0
Задачка с дробями.
    #38132712
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaN, maytonЭто Вы сейчас с кем разговариваете?Есть люди, которые неровно дышат на мои утверждения.
...
Рейтинг: 0 / 0
25 сообщений из 131, страница 2 из 6
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка с дробями.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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