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 ]
Заголовок сообщения: 
Что то я не пойму. Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел. :shuffle; ???
Комбинации (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 каждый, где в самом вложенном цикле будет находиться максимальный из индексов, а затем проверяться меньше ли он суммы двух других.
Что-то вроде такого (пардон за архаичный стиль :oops: и отсутствие оптимизации внутреннего цикла) :
----------------------------------------------------------
: 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 и попробуйте треугольник с такими длинами построить.
В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи

Ну ладно сразу ногами пинать :cry:
Ну не подумал. действительно a+b >c
Страница 1 из 3 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/