Forth http://fforum.winglion.ru/ |
|
"Треугольные" тройки чисел http://fforum.winglion.ru/viewtopic.php?f=19&t=2397 |
Страница 1 из 3 |
Автор: | chess [ Чт янв 21, 2010 15:24 ] |
Заголовок сообщения: | "Треугольные" тройки чисел |
Навеяно "треугольной" задачей студента: Дан отрезок натурального ряда чисел от 1 до N. Найти в нем количество таких троек чисел, каждой из которых соответствует треугольник со сторонами, равными значениям чисел в тройке. Решение дать в следующем виде: Код: : Q3 ( N -- Q ) ..... ;
|
Автор: | _Harry [ Чт янв 21, 2010 16:18 ] |
Заголовок сообщения: | |
Что то я не пойму. Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел. ??? Комбинации (1 2 2) (2 2 1) (2 1 2) считаются за одну или как? |
Автор: | mOleg [ Чт янв 21, 2010 16:34 ] |
Заголовок сообщения: | |
я думаю, что имелись ввиду прямоугольные треугольники |
Автор: | Варнак [ Чт янв 21, 2010 16:53 ] |
Заголовок сообщения: | |
mOleg писал(а): я думаю, что имелись ввиду прямоугольные треугольники
необязательно, вовсе не любые три числа могут быть длинами сторон треугольника |
Автор: | Варнак [ Чт янв 21, 2010 16:54 ] |
Заголовок сообщения: | |
mOleg писал(а): я думаю, что имелись ввиду прямоугольные треугольники
необязательно, вовсе не любые три числа могут быть длинами сторон треугольника |
Автор: | chess [ Чт янв 21, 2010 17:10 ] |
Заголовок сообщения: | |
_Harry писал(а): Что то я не пойму. Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел. ???
Комбинации (1 2 2) (2 2 1) (2 1 2) считаются за одну или как? В каждой тройке всегда числа все разные, так как в ряду натуральных чисел нет двух одинаковых чисел. Кроме того все тройки разные по набору чисел, таким образом (2 3 4) и (2 4 3) это тройки одинаковые (по набору чисел) и учитывать в общем количестве троек нужно только одну тройку. Можно еще сказать, что каждой из троек будут соответствовать уникальные, между собой не совпадающие треугольники. |
Автор: | garbler [ Чт янв 21, 2010 19:47 ] |
Заголовок сообщения: | |
Варнак писал(а): mOleg писал(а): я думаю, что имелись ввиду прямоугольные треугольники необязательно, вовсе не любые три числа могут быть длинами сторон треугольника требование одно единственное: А+Б > В не интересно |
Автор: | WingLion [ Чт янв 21, 2010 21:25 ] |
Заголовок сообщения: | |
garbler писал(а): требование одно единственное: А+Б > В ой ли? для чисел A,B,C этo требованиe - A+B<C или A+C<B или B+C<A _Harry писал(а): Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел.
Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить. В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи |
Автор: | вопрос [ Чт янв 21, 2010 23:28 ] |
Заголовок сообщения: | |
WingLion писал(а): garbler писал(а): требование одно единственное: А+Б > В ой ли? для чисел A,B,C этo требованиe - A+B<C или A+C<B или B+C<A _Harry писал(а): Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел. Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить. В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи Да, кажется, это так, в т. случае алгоритм последователен и выглядит так - для каждого числа а (от 1) - найти все пары дополняющих чисел a =< b , b =< c, c < N , чтобы ( b + c > a ) но и ( b + а > с ) - до тех пор, пока такие пары вообще находятся - т.е. при некотором а (которое у нас будет линейно возрастать 1 2 3 4 5 6 и т.д.) возможности чисел меньших N перестанут соответствовать условиям |
Автор: | Hishnik [ Пт янв 22, 2010 00:36 ] |
Заголовок сообщения: | |
Для каждого из сочетаний первых двух чисел необходимо выбрать такие третьи числа, чтобы они были больше суммы двух первых (согласно аксиоме треугольника). При этом для числа N второе число будет как минимум 1, а значит, третьей стороны уже не будет (она должна равняться N+2). Для числа N - 1 ее тоже не будет, а вот для N - 2 будет один вариант - вторая сторона равна 1, и третья тоже равна 1. Для каждого последующего числа будет на один вариант третьей стороны больше. И так далее. Получается комбинаторика. |
Автор: | Варнак [ Пт янв 22, 2010 08:12 ] |
Заголовок сообщения: | |
Хищник писал(а): Для каждого из сочетаний первых двух чисел необходимо выбрать такие третьи числа, чтобы они были больше суммы двух первых (согласно аксиоме треугольника). При этом для числа N второе число будет как минимум 1, а значит, третьей стороны уже не будет (она должна равняться N+2). Для числа N - 1 ее тоже не будет, а вот для N - 2 будет один вариант - вторая сторона равна 1, и третья тоже равна 1. Для каждого последующего числа будет на один вариант третьей стороны больше. И так далее. Получается комбинаторика.
Эта, извиняюсь, "комбинаторика", несущественно (в конечное число раз, но не изменит порядка) сократит трудоёмкость очевидного алгоритма - O(N^3), заключающегося в переборе всех элементов трехмерного массива, т.е. трех вложенных циклов от 1 до N каждый, где в самом вложенном цикле будет находиться максимальный из индексов, а затем проверяться меньше ли он суммы двух других. Что-то вроде такого (пардон за архаичный стиль и отсутствие оптимизации внутреннего цикла) : ---------------------------------------------------------- : QQQ ( N > Q) 0 SWAP DUP 0 DO DUP 0 DO 0 DO I J K 3MAX I J K 3MIN I J K 3MIDDLE + < IF 1+ THEN LOOP LOOP LOOP ; ---------------------------------------------------------- где 3MAX, 3MIN и 3MIDDLE оставляют, соответственно, максимальное, минимальное и среднее число из трёх лежащих на стеке. |
Автор: | WingLion [ Пт янв 22, 2010 09:28 ] |
Заголовок сообщения: | |
пост прибит, чтобы глупость у всех на виду не блестела... |
Автор: | Hishnik [ Пт янв 22, 2010 10:09 ] |
Заголовок сообщения: | |
Вообще, задача из серии тестов на собеседовании: "напишите программу, печатающую сумму целых чисел от 1 до 100". Правильный ответ printf("5050"), поскольку никто не ставил задачу сосчитать, только напечатать... |
Автор: | Варнак [ Пт янв 22, 2010 10:10 ] |
Заголовок сообщения: | |
WingLion писал(а): Задача имеет четкое теоретическое решение ...
У таких задач (а их иногда предлагают школьникам на разных олимпиадах) есть интересный аспект (особенно когда ограничен диапазон входных данных): что быстрее - вывести формулу и посчитать по ней или набросать программку, которая посчитает. |
Автор: | _Harry [ Пт янв 22, 2010 11:32 ] |
Заголовок сообщения: | |
WingLion писал(а): Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить.
В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи Ну ладно сразу ногами пинать Ну не подумал. действительно a+b >c |
Страница 1 из 3 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |