Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 00:32

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: "Треугольные" тройки чисел
СообщениеДобавлено: Чт янв 21, 2010 15:24 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Навеяно "треугольной" задачей студента:
Дан отрезок натурального ряда чисел от 1 до N.
Найти в нем количество таких троек чисел, каждой из которых
соответствует треугольник со сторонами, равными значениям чисел в тройке.
Решение дать в следующем виде:
Код:
: Q3  ( N -- Q )  .....  ;

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 16:18 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
Что то я не пойму. Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел. :shuffle; ???
Комбинации (1 2 2) (2 2 1) (2 1 2) считаются за одну или как?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 16:34 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
я думаю, что имелись ввиду прямоугольные треугольники :)

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 16:53 
Не в сети

Зарегистрирован: Пн окт 15, 2007 17:24
Сообщения: 164
Откуда: Бийск
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
mOleg писал(а):
я думаю, что имелись ввиду прямоугольные треугольники :)

необязательно, вовсе не любые три числа могут быть длинами сторон треугольника :?

_________________
And so forth ...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 16:54 
Не в сети

Зарегистрирован: Пн окт 15, 2007 17:24
Сообщения: 164
Откуда: Бийск
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
mOleg писал(а):
я думаю, что имелись ввиду прямоугольные треугольники :)

необязательно, вовсе не любые три числа могут быть длинами сторон треугольника :?

_________________
And so forth ...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 17:10 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
_Harry писал(а):
Что то я не пойму. Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел. ???
Комбинации (1 2 2) (2 2 1) (2 1 2) считаются за одну или как?

В каждой тройке всегда числа все разные, так как в ряду натуральных чисел нет двух одинаковых чисел.
Кроме того все тройки разные по набору чисел, таким образом (2 3 4) и (2 4 3) это тройки одинаковые (по набору чисел) и учитывать
в общем количестве троек нужно только одну тройку. Можно еще сказать, что каждой из троек будут соответствовать уникальные, между собой
не совпадающие треугольники.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 19:47 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Варнак писал(а):
mOleg писал(а):
я думаю, что имелись ввиду прямоугольные треугольники :)

необязательно, вовсе не любые три числа могут быть длинами сторон треугольника :?

требование одно единственное: А+Б > В

не интересно :-(


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 21:25 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
garbler писал(а):
требование одно единственное: А+Б > В


ой ли?
для чисел A,B,C этo требованиe - A+B<C или A+C<B или B+C<A

_Harry писал(а):
Это же любые ( надо полагать не повторяющиеся) комбинации из трех чисел.

Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить.
В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 21, 2010 23:28 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
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 перестанут соответствовать условиям


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 22, 2010 00:36 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Для каждого из сочетаний первых двух чисел необходимо выбрать такие третьи числа, чтобы они были больше суммы двух первых (согласно аксиоме треугольника). При этом для числа N второе число будет как минимум 1, а значит, третьей стороны уже не будет (она должна равняться N+2). Для числа N - 1 ее тоже не будет, а вот для N - 2 будет один вариант - вторая сторона равна 1, и третья тоже равна 1. Для каждого последующего числа будет на один вариант третьей стороны больше. И так далее. Получается комбинаторика.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 22, 2010 08:12 
Не в сети

Зарегистрирован: Пн окт 15, 2007 17:24
Сообщения: 164
Откуда: Бийск
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
Хищник писал(а):
Для каждого из сочетаний первых двух чисел необходимо выбрать такие третьи числа, чтобы они были больше суммы двух первых (согласно аксиоме треугольника). При этом для числа 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 оставляют, соответственно, максимальное, минимальное и среднее число из трёх лежащих на стеке.

_________________
And so forth ...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 22, 2010 09:28 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
пост прибит, чтобы глупость у всех на виду не блестела...

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Последний раз редактировалось WingLion Пт янв 22, 2010 23:00, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 22, 2010 10:09 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Вообще, задача из серии тестов на собеседовании: "напишите программу, печатающую сумму целых чисел от 1 до 100". Правильный ответ printf("5050"), поскольку никто не ставил задачу сосчитать, только напечатать... :)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 22, 2010 10:10 
Не в сети

Зарегистрирован: Пн окт 15, 2007 17:24
Сообщения: 164
Откуда: Бийск
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
WingLion писал(а):
Задача имеет четкое теоретическое решение ...

У таких задач (а их иногда предлагают школьникам на разных олимпиадах) есть интересный аспект (особенно когда ограничен диапазон входных данных): что быстрее - вывести формулу и посчитать по ней или набросать программку, которая посчитает.

_________________
And so forth ...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 22, 2010 11:32 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
WingLion писал(а):
Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить.
В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи

Ну ладно сразу ногами пинать :cry:
Ну не подумал. действительно a+b >c


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу 1, 2, 3  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB