Интересные интересности и задачи/головоломки

[Sibedir]

Да, действительно, производительность такая же, но запись короче и нагляднее.

Кстати, странно, я этот Frac тоже мучал, но у меня не получалось. И я, кстати, использовал TDoubleHelper.Frac.

[Poma][a]

Принесли Вам пиццу. Вам разрешается сделать 6 разрезов по-прямой. На какое максимальное кол-во кусков Вы можете разрезать пиццу? (Куски могут быть <>)

[BDA]

Poma][a, 22?
Алго:
разрез - кол-во кусков
1 разрез - 2 куска
2 разрез - 4 куска
3 разрез (пересекает предыдущие два в разных точках) - 7
и тд, т.е. каждый следующий должен пересекать предыдущие в разных точках (а не в пересечении нескольких предыдущих разрезов).

Сообщение от Poma][a

Верно! А где пруф?

Уже добавил.

[Poma][a]

Верно! А где пруф?

[Аватар]

Кстати почти баян, одна девица уже просила алгоритм нахождения максимального количества кусков полученных n разрезами или что-то в этом духе. В прошлом году кажись, в разделах для начинающих

[Poma][a]

Аватар,
Спасибо!, вот и сама тема :тыц (надо будет почитать на досуге )

Уже добавил.

Угу!

[Poma][a]

И так задача :
Найти число от 1 до N включительно такое, что в разложении его на простые множители кол-во множителей максимально. Если таких числе несколько, выбрать максимальное из них.
Например, найдем разложение на простые множители чисел от 1 до 7. Числа 2, 3, 5 и 7 простые, в их разложении по 1-му множителю. В разложении числа 1 ноль простых множителей. В разложении чисел 4 = 2 * 2 и 6 = 2 * 3 по 2 простых множителя. Значит ответом задачи для N = 7 будет являться число 6.

[Abstraction]

Найти число от 1 до N включительно такое, что в разложении его на простые множители кол-во множителей максимально. Если таких числе несколько, выбрать максимальное из них.

Ответ: K=floor(log2(N)) - количество множителей. D3 = floor(log_3/2(N/2^K)) - степень тройки в целевом числе, D2=K-D3 - степень двойки. Число - 2^D2 * 3^D3.

[Poma][a]

[SPOILER]Мне кажется, что Вы слегка перемудрили. Вы совершенно верно заметили что существует связь между ответом и степенями двойки (и если уж выкладывать все карты на стол, то и тройка имеет своё место в решении). Мне кажется, что Вы неправильно высчитываете кол-во 3-к.. Поэтому не могли бы Вы представить Ваше решение в словесной форме или же переписать всё написанное в посте#729 в Pascale'подном синтаксисе (что опровергнуть либо подтвердить мои догадки) [/SPOILER]

[Abstraction]

Моё решение и так в словесной форме, как бы. Но пожалуйста:
По очевидным причинам, искомое число имеет вид 2^a * 3^b. Поскольку любой простой множитель больше 4 можно заменить на две двойки, уменьшив число и увеличив количество множителей. Также очевидно, что a+b = K = floor(log2(N)), так как 2^K <= N < 2^(K+1). Искомое число также максимально, то есть при том же количестве множителей его нельзя увеличить: 2^a * 3^b <= N < 2^(a-1) * 3^(b+1). Поделив на 2^K и взяв логарифм по основанию 3/2, имеем: b <= log_3/2(N/2^K) < b+1, что даёт b = floor(log_3/2(N/2^K)) и a = K-b. Разумеется, точное вычисление этого выражения на компьютере может быть затруднено, особенно при больших N - возможна ошибка на единицу.