Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Ср сен 26, 2018 08:54

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 22, 2010 14:56 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2120
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
Эта задача не на вывод формулы, по которой можно посчитать результат просто подставив в формулу заданное значение.
Число операций для получения результата в данном случае зависит от значения исходных данных, то есть формула будет меняться в зависимости от N.
Такие формулы записывают с помощью операторов повторения.
Ну вот мое решение как иллюстрация:
Код:
: Q3 ( N -- Q )
>R R@ 1- DUP 1- R@ * * 6 /  \ число сочетаний из N по 3
0  \ счетчик числа троек
R@ \ N
R> 2/ 1+ 1
DO
  DUP I 2* - DUP 1+ * 2/ ROT + SWAP  \ подсчет числа "нетреугольных" троек
LOOP
DROP - ;

Код:
\ TEST

: TR 1+ 3 DO I Q3 CR . LOOP ;

33 TR

лог
Код:
0
1
3
7
13
22
34
50
70
95
125
161
203
252
308
372
444
525
615
715
825
946
1078
1222
1378
1547
1729
1925
2135
2360
2600
Ok

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


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

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Народу явно надо теорему косинусов вспомнить - про третью сторону. Решений будет больше,- так для треугольника с двумя сторонами равными 1 и разным углом между ними будет целый список длины третьей стороны.
Задача относятся к комбинаторной, как видится с первого взмаха ресницой. Тут ксати и и не поленится можно алгоритм свести к параллельно выполняемым действиям.


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2120
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
Варнак писал(а):
Эта, извиняюсь, "комбинаторика", несущественно (в конечное число раз, но не изменит порядка) сократит трудоёмкость очевидного алгоритма - O(N^3),

Сложность алгоритма (в идеале конечно) должна соответствовать сложности задачи, в данном случае она как не странно O(N). Полный перебор как правило освобождает от выявления скрытых связей между данными задачи, но дает самое неэффективное решение.

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


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

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
chess писал(а):
Полный перебор как правило освобождает от выявления скрытых связей между данными задачи, но дает самое неэффективное решение

Небольшая ремарка : Зато дает проверить адекватность решения


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Alexander писал(а):
Народу явно надо теорему косинусов вспомнить - про третью сторону. Решений будет больше,- так для треугольника с двумя сторонами равными 1 и разным углом между ними будет целый список длины третьей стороны.


список из одного числа - 1? Задача то для

Цитата:
натурального ряда чисел от 1 до N.

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


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

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
всегда любил читать через слово ))
на самом деле если вы вспомните теорему косинусов и наложите ограничения на числа то вам надо будет проверить квадрыты натуральных чисел для третьей стороны. т.е. проверить найдется ли такой косинус котрый даст треугольник с числами из натурального множества


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

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

ой, какое интересное слов... а оно тут каким боком?

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


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

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
в общем: A ,B, C -длины сторон, ну и стороны, треугольника. Изветно С<A+B или С=A+B-x, где х принадлежит натуральному множеству, впрочем как и A ,B, C. По теореме косинусов выразим угол между сторанами A и B = (A^2+B^2-C^2)/(2*A*B), ну и конечо же это все меньше 1 по модулю (неравенство строгое) получим |A^2+B^2-(A+B-X)^2|-2*A*B<0, ну и ищем число сколько раз можно подставить X для удовлетворения неравентсва с различными парами чисел A,B.
Ну вот математика гласить так.


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 318
Благодарил (а): 1 раз.
Поблагодарили: 7 раз.
a вот как я сделал:
Код:
: q3 ( n -- q )
  1+ 0 over 1 do     \ i = 1 .. n
    over i do       \ j = i .. n
      over i j + min i do
        1+
      loop
    loop
  loop
  swap drop
;

: test 33 1 do i q3 cr . loop ; test

1
3
7
13
22
34
50
70
95
125
161
203
252
308
372
444
525
615
715
825
946
1078
1222
1378
1547
1729
1925
2135
2360
2600
2856
3128


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2120
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
forther писал(а):
a вот как я сделал:

Выглядит кратко, но при ближайшем рассмотрении очень медленный вариант.
сравним варианты:

Код:
: forther 1000 q3 ;
: chess   1000 Q3 ;

REQUIRE METER ~CHESS\TASK\METER.F

STARTLOG
METER forther
METER chess

лог
Код:
521252451 521555310
5688 5553
Ok

что и требовалось доказать.

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


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

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Если вдуматься, то для каждой пары существует гипотетичеких 2(A+B)-1... вариантов треугольников с длиной стороны С,
Остается исключить не подходящие и повернутые (повторяющиеся в разлчной ротации тройки чисел) треугольники.
Так для случая когда стороны A и B равны 1, - имеем равносторонний треугольник.


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 318
Благодарил (а): 1 раз.
Поблагодарили: 7 раз.
chess писал(а):
forther писал(а):
a вот как я сделал:

Выглядит кратко, но при ближайшем рассмотрении очень медленный вариант.
сравним варианты:

Код:
: forther 1000 q3 ;
: chess   1000 Q3 ;

REQUIRE METER ~CHESS\TASK\METER.F

STARTLOG
METER forther
METER chess

лог
Код:
521252451 521555310
5688 5553
Ok

что и требовалось доказать.


бесспорно!

интересно, а аналитическое решение кто нибудь покажет?


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 318
Благодарил (а): 1 раз.
Поблагодарили: 7 раз.
chess, a вот эту программку не прогоните через свой METER?
Код:
: q3" ( n -- q )
  0 over 1 do          \ j = 1 .. n
    over i - 0 do      \ i = 0 .. n-j
      i j min +
    loop
  loop
  swap drop
;


EDIT: уже не надо


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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4952
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
мндя, у мя получаются другие числа.
Для того, чтобы получился треугольник, нужно, чтобы сумма двух других сторон была больше на 1 самой длинной.
то есть, для длины в 1, возможен только один равносторонний треугольник с длинами 1+1
<pre>
для 2: 2+2;2+1 = 2 варианта
для 3: 3+3;3+2;3+1
2+2 = 4 варианта
для 4: 4+4;4+3;4+2;4+1
3+3;3+2 = 6 вариантов
для 5: 5+5;5+4;5+3;5+2;5+1
4+4;4+3;4+2
3+3 = 9 вариантов
12
16
20
25
и так далее.
</pre>

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


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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4952
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
таким образом считать ничего не надо особо.
<pre>
: Count ( u --> # )
0 >R
BEGIN DUP 0 > WHILE
DUP R+
2 -
REPEAT DROP
R> ;

\ и подсчет ряда:
: triangles ( u --> )
BEGIN DUP WHILE
DUP Count . CR
1 -
REPEAT DROP ;
</pre>

лог:
<pre>
FORTH(0)>20 triangles
110
100
90
81
72
64
56
49
42
36
30
25
20
16
12
9
6
4
2
1
</pre>

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


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

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


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

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


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

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