Имя: Пароль:
IT
 
Правильный треугольник на клетчатой бумаге
0 Михаил Козлов
 
06.06.12
14:50
На листке клетчатой бумаги 100х100 клеток разместить треугольник с вершинами в узлах, наиболее приближенный к правильному.
1 vde69
 
06.06.12
14:53
основание под 30градусов ???
2 Mikeware
 
06.06.12
14:55
бедняга. Задачка для 5 класса
3 Xapac_2
 
06.06.12
15:01
ставишь 3 точки и соединяешь по линейке. какие сложности?
4 palpetrovich
 
06.06.12
15:02
87 :)
5 aka AMIGO
 
06.06.12
15:03
(1)под 60

(0) рисуешь основание, измеряешь длину циркулем, делаешь 2 засечки из окончаний прямой-основания.. вроде всё..
6 raipo
 
06.06.12
15:04
(4) - долго описывать?
основание - 100 клеток, из середины восстанавливаем перпендикуляр и отсчитываем 87 клеток
7 Xapac_2
 
06.06.12
15:05
стоп а что такое "правельный" треугольник?
8 vde69
 
06.06.12
15:05
кстати какой критерий "наиболее приближенный к правильному"

1. отколение в мм от идеальной точки
2. отклонение углов от 60гр
3. относительная длина

и т.д.

что есть мерило?
9 MadHead
 
06.06.12
15:05
(5) я так понимаю без циркуля надо это сделать. По теореме синусов иил косинусов рассчитай высоту и пол стороны
10 MadHead
 
06.06.12
15:06
блин не по теореме, а через синус или косинус угла
11 trad
 
06.06.12
15:07
(5) "с вершинами в узлах"
я так понимаю вершины должны быть на пересечении разлиновки
12 palpetrovich
 
06.06.12
15:08
(8) наверное не зря там про "клеточки" :)
13 vde69
 
06.06.12
15:09
решение можно сделать так

из угла под проводим 2 линии под улами 15 и 75 градусов, на этих линиях ищим точку где она пересечет центр клеточки (а она гарантировано пересекает, вроде 1/8 клеткам, или 16), дальше соеденяем.

треугольник будет ТОЧНО ПРАВИЛЬНЫМ
14 palpetrovich
 
06.06.12
15:11
(11) упс, по-ходу в (4) я прогнал, задачка-то с подковыркой. наверняка есть другое целое основание, при котором с целой-же высотой треугольник будет "точнее"
15 mozzga
 
06.06.12
15:11
шесть клеток вправо три вверх в вот угол поделен на 30 и 60 грудусов
16 acsent
 
06.06.12
15:12
(8) минимальная разница между мин и макс стороной
17 palpetrovich
 
06.06.12
15:13
+(14) к примеру основание 6, высота 4
18 MadHead
 
06.06.12
15:14
(15) врядли )
19 NcSteel
 
06.06.12
15:14
на клетке легко сделать 60 градусов угол. Далее от него плясать.
20 acsent
 
06.06.12
15:14
остальные стороны будут по 5
21 vde69
 
06.06.12
15:15
вариант 1

первая точка 0.0
вторая точка 4.1
третья точка 1.4

-----------------------------
вариант 2

первая точка 0.0
вторая точка 8.2
третья точка 2.8


и так далее
22 NcSteel
 
06.06.12
15:16
(19) + Либо зная длину катетов прямоугольного треугольника при углах в 60 и 30 градусов, то можно лугко получить правильный треугольник
23 acsent
 
06.06.12
15:17
(21) это не правильный тр-ник.
24 acsent
 
06.06.12
15:18
а если он неправильный, то нужно доказывать
25 vde69
 
06.06.12
15:19
(23) это почти правильный :) просто мне лень считать 15г через какие точки проходит
26 NcSteel
 
06.06.12
15:19
(22) + Используя торему синусов (или косинусов уже не помню) + x^2 = a^2 + b^2 Можно лугко получить длину большого катета. Малый равен 50 = (100 / 2)
27 palpetrovich
 
06.06.12
15:19
(21) я так понимаю клетки должны быть целыми
28 NcSteel
 
06.06.12
15:20
(27) Ваши домыслы.
29 raipo
 
06.06.12
15:21
так есть же ответ уже - первая точка (0,0)
вторая - (100,0)
третья - (50,87)
30 sapphire
 
06.06.12
15:21
(0)
A(x,y)=(0,0)
B(x,y)=(5,8.6)=(5,5*tg(3.1428/3))
C(x,y)=(10,0)
31 sapphire
 
06.06.12
15:22
(0) Для 100
A(x,y)=(0,0)
B(x,y)=(50,86)=(50,50*tg(3.1428/3))
C(x,y)=(100,0)
32 sapphire
 
06.06.12
15:22
(29) Точно :)
33 Mikeware
 
06.06.12
15:23
знаменитый прямоугольнфй треугольник 3-4-5 имеет погрешность от 30-60 градусов около 2%. Вполне достаточно.
34 Михаил Козлов
 
06.06.12
15:24
Тангенс 60 (отношение высоты к половине основания ) = КОРЕНЬ(3), а это число иррациональное, поэтому совсем правильный (с вершинами в узлах) не построить.
50 и 87 - не самый лучший.
35 palpetrovich
 
06.06.12
15:27
(33) не, у этого знаменитого основание = 6, а стороны=5  :)
36 acsent
 
06.06.12
15:27
можно конечно состваить уравнение для (16), взять производную, наэти экстремуму, но влом
37 Шапокляк
 
06.06.12
15:27
(13) А зачем так? У правильного треугольника все углы по 60 градусов. Какие 30 градусов в углах?
(0) Высота у правильного треугольника составляет со сторонами угол 30 градусов. Известно также, что в прямоугольном треугольнике сторона, лежащая против угла 30 градусов, вдвое меньше гипотенузы. Соответственно, рисуем треугольник, у которого с - длина стороны, h - высота, при этом h=SQRT(3)*c/2. Если мы размещаем горизонтально основание с, и при этом оно составляет по длине целое число клеточек, то высота никак не может быть целым числом. Нетрудно видеть, что можно подобрать такое основание, при котором высота наиболее приближена к целому числу, а треугольник к правильному.
38 Михаил Козлов
 
06.06.12
15:28
(33) Речь не о том, достаточно или нет, а о "лучшем" варианте (угол при основании наиболее близок к 60).
39 vde69
 
06.06.12
15:28
самый правильный, расхождения менее 0.1%

0.0
100.39
39.100
40 acsent
 
06.06.12
15:29
(37) ты ограничиваешь себя стороной полностью лежащей на линии, а это не обязательно
41 Михаил Козлов
 
06.06.12
15:30
(36) Экстремум придется брать по целым точкам и можно, вернеее, точно натолкнешься на локальный экстремум. Проще в Экселе прогнать.
42 Шапокляк
 
06.06.12
15:31
(40) Тогда вообще нет ограничений. Строна 100, высота вверх их середины стороны - посчитай, поставь точку и соедини. Впрочем, в (00 вроде про клетки сказано?
43 acsent
 
06.06.12
15:31
(41) но задача же не на такое решение в лоб ))
44 Михаил Козлов
 
06.06.12
15:32
(39) В оптимуме 0,02%.
45 acsent
 
06.06.12
15:32
и вообще треугольник может быть неравнобедренным
46 acsent
 
06.06.12
15:32
или нет?
47 raipo
 
06.06.12
15:34
(44) так что в (39) решение или нет?
48 acsent
 
06.06.12
15:35
собственно задача найти или доказать?
49 Шапокляк
 
06.06.12
15:35
Пипец правильный треугольник в (39) - две стороны по 107 и одна 86!
50 vde69
 
06.06.12
15:35
в екселе проганл, оптимальное

0,0
85,22
22,85

отклонениеие от идельной точки 0,000381166
51 Михаил Козлов
 
06.06.12
15:39
(50) У меня получилось основание - 82, высота 71, отклонение -0,00034349
У другим методом такой же ответ.
52 palpetrovich
 
06.06.12
15:41
де-то я слажал :))
   Для МалыйКатет = 1 по 100 Цикл
       МинимальнаяРазница = 1000;
       ИскомаяГипотенуза = МалыйКатет*2;
       Для БольшойКатет = МалыйКатет по ИскомаяГипотенуза Цикл // грубо
           Разница = Pow(ИскомаяГипотенуза,2)- Pow(БольшойКатет,2) + Pow(МалыйКатет,2);
           Если Разница < МинимальнаяРазница Тогда
               МинимальнаяРазница = Разница;
               НужныйМалыйКатет = МалыйКатет;
           КонецЕсли;    
       КонецЦикла;    
   КонецЦикла;    
   Сообщить("НужныйМалыйКатет " + НужныйМалыйКатет);
53 NcSteel
 
06.06.12
15:41
Если в школе нужен был правильный треугольник , то рисовал его так:

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

Итог: Высота 75, основание 100.
54 Шапокляк
 
06.06.12
15:42
(50) И все стороны равны? Или какой там критерий?
В общем, самый равносторонний треугольник такой: чертим горизонтальный отрезок 52 , делим его пополам, откладываем от середины высоту 45 и все точки соединяем.
55 vde69
 
06.06.12
15:42
(51) посчитай мой треугольник, просто я не понял как ты на основании 82 получил лучший результат
56 acsent
 
06.06.12
15:44
апочему решили что корень из 3 нельзя построить, ведь корень из 2 можно ведь
57 aka AMIGO
 
06.06.12
15:44
Sin(60град) = 0.8660
т.е. высота равностороннего треугольника = 0.8660 основания.

отседова примерно следует: Если основание = 1000ед, то вершина точно будет отстоять от него точно на 866 квадратиков..
больше ничего не придумывается :)
58 Шапокляк
 
06.06.12
15:45
(51) да, извиняюсь за (54) - этот самый оптимальный, между корнем из 3 и высотой всего 0.01!
59 aka AMIGO
 
06.06.12
15:45
а 0.8660 - корень из 2 деленное на 2
60 NcSteel
 
06.06.12
15:45
(57) +1 .
61 aka AMIGO
 
06.06.12
15:45
пардон, корень из 3 деленное на 2
62 Мимо Проходил
 
06.06.12
15:50
Если критерий - минимизировать разницу межу максимальной и минимальной стороной, то это точка.
63 Михаил Козлов
 
06.06.12
16:23
(52) Можно и программно, но в Вашем варианте число операций квадратично по числу клеток (100), а можно за LOG.
64 vde69
 
06.06.12
16:26
0,0
41,11
11,41

разница длин сторон составляет 0,055540132% или 0,023563682 клетки
65 palpetrovich
 
06.06.12
16:29
(63) не, там слажал, потом малехо поправил, но все-равно более верный результат в (51) не получил
   МинимальнаяРазница = 100;
   Для МалыйКатет = 1 по 50 Цикл
       ИскомаяГипотенуза = МалыйКатет*2;
       БольшойКатет = Sqrt(Pow(ИскомаяГипотенуза,2)- Pow(МалыйКатет,2));
       Разница0 = БольшойКатет - Окр(БольшойКатет, 2, 0);
       Разница1 = Окр(БольшойКатет, 2, 1) - БольшойКатет;
       Разница = ?(Разница0<Разница1,Разница0,Разница1);
       Если Разница < МинимальнаяРазница Тогда
           МинимальнаяРазница = Разница;
           НужныйМалыйКатет = МалыйКатет;
           НужныйБольшойКатет = БольшойКатет;
           ИскомаяГипотенуза = Pow(НужныйБольшойКатет,2) +  Pow(НужныйМалыйКатет,2);
       КонецЕсли;    
   КонецЦикла;    
   Сообщить("МалыйКатет " + НужныйМалыйКатет + " БольшойКатет "+ НужныйБольшойКатет+"  Гипотенуза "+ИскомаяГипотенуза);
// МалыйКатет 22 БольшойКатет 38,1051177665153  
у мну погрешность больше :)
66 RomanYS
 
07.06.12
11:02
Лучший на поле 100*100
(0,0) (15,56) (56,15) Дельта 0,0086238947539
Есть лучше, но слегка не влезет в 100*100:
(0,0) (56,97) (112,0) 0,004464196745

<code>
   к = Sqrt(3)/2;
   МинДельта = 1;
   Для  х =  1 По 100 Цикл
       Для  у =  0 По 100 Цикл
           х1 = Окр(х/2 + к*у);
           у1 = Окр(у/2 - к*х);
           
           Дл1 = Sqrt(х*х+у*у);
           Дл2 = Sqrt(х1*х1+у1*у1);
           Дл3 = Sqrt((х1-х)*(х1-х)+(у1-у)*(у1-у));
           
           Дельта = Макс(Дл1, Дл2, Дл3) - Мин(Дл1, Дл2, Дл3);
           
           Если МинДельта > Дельта Тогда
               МинДельта = Дельта;
               Сообщить(""+Дельта + "    ("+х+","+у+")    ("+х1+","+у1+")");
           КонецЕсли;
       КонецЦикла;

</code>
67 palpetrovich
 
07.06.12
17:51
(66) в (51) погрешность меньше. А вообще - забавно, я даже возможность поворота теугольника не рассматривал... :)
68 RomanYS
 
07.06.12
20:43
(67) в (51):
-0,012196029=КОРЕНЬ(71*71+41*41)-82
69 Михаил Козлов
 
07.06.12
20:57
(68) Не проверял, скорее всего Вы правы.
Я как-то заложился на горизонтальное основание - виноват.
В этом случае задача сводится к поиску целых p и q (p<=100, q<=50), так что p/q наилучшим образом приближает SQRT(3).
По этой теме есть интересный аппарат цепных дробей (wiki:%CD%E5%EF%F0%E5%F0%FB%E2%ED%E0%FF_%E4%F0%EE%E1%FC), который позволяет очень быстро находить такие числа. Советую почитать, особенно приложения.
В частности, для ПИ: 3, 22/7, 333/106, 355/113, 103993/33102.
Значением 22/7 часто пользовались греки (архимедово приближение).
Гюйгенс, когда делал механическую модель солнечной системы, тоже их использовал.
Первый пример трансцендетного числа привел Лиувилль (году этак в 1841), основываясь на неполных частных.
70 Михаил Козлов
 
08.06.12
13:26
(68) Проверил Ваше решение: оно оказалось хуже (51) (точность чисел - 12).
У Вас тангенс угла при основании = 1,732738095238, угол = 60,009841741648
Для (51) = 1,731707317073, угол = 59,99507913
У Вас отклонение по углу = -0,009841741648
Для (51) = 0,004920871, т.е. в 2 раза меньше.
71 andydddd
 
08.06.12
15:20
(0, 0) (41, 71) (82, 0)
отношения сторон 1,0001487 и 1
72 andydddd
 
08.06.12
15:22
еще (0, 0) (26, 97) (97, 26) хорошо подхоит
73 Михаил Козлов
 
08.06.12
15:37
(72) Отклонение по углу = 0,009840765720, что в 2 раза хуже (51)
(71) = (51).
Пока что (51) - лучший.
Вообще-то речь не о том, как программно получить лучшее решение. Простым перебором (трудоемкость - размер листа^2) можно найти решение.
Цель топика была обратить внимание на цепные (непрерывные) дроби, как очень эффективный (трудоемкость - логарифм от размера) инструмент в задачах, когда нужно приближать числа рациональными (с не очень большими знаменателями).
В частности, для приближения SQRT(3) с числителем и знаменателем<=100 нужное неполное частное получается на 6-м шаге.
74 vde69
 
08.06.12
15:39
(73) а (64) как?
75 vde69
 
08.06.12
15:44
(73) программно совсем не размер листа, все гораздо проще

первая точка всегда 0.0
вторая точка лежит в сегменте 15градусов от точки 0.0
третья точка определяется как одна из 4х

то есть простой перебор с размером листа Х это примерно х*х/2 то есть половина точек, а при небольшей оптимизацией 1/8 от количества точек
76 Михаил Козлов
 
08.06.12
15:45
(74) Отклонение по углу = 0,036721262301. В 7 раз хуже (51).
77 Михаил Козлов
 
08.06.12
15:47
(75) Что N^2, что N^2/2, что N^2/8 - порядок N^2. А неполные частные позволяют за LOG(N).
78 vde69
 
08.06.12
15:51
(77) логарифмы считаются сильно дольше чем корни.

думаю, что задачу можно решать путем бинарных операций
79 155153144627
 
08.06.12
15:52
http://s019.radikal.ru/i639/1206/4c/a988886b754e.jpg
Я вот так сделал :-)
80 155153144627
 
08.06.12
15:54
Разместил на листке и пох что он в клетку...
81 Михаил Козлов
 
08.06.12
15:55
(77) Не логарифмы считаются, а количество операций О(log(N)), где N - размерность задачи (число клеток). Для N = 1000 у Вас будут сотни тысяч, а в неполных частных - десятки.
82 Михаил Козлов
 
08.06.12
15:57
(80) Извините, не понял.
83 155153144627
 
08.06.12
16:03
(82) Сложи листок попалам вдоль, и совмести уголок с линией сгиба, отметь точку. Соедини углы с точкой.
84 Михаил Козлов
 
08.06.12
16:15
(83) У Вас равносторонний треугольник, но вершина не попадет в узел. Речь не о том, как построить правильный треугольник - Вы, по сути воспользовались нижней стороной листа, как циркулем.
85 DailyLookingOn Sunset
 
08.06.12
16:18
Проверил (51) и (66).
Соотношение всех сторон одинаковое и равно sqrt(2). Т.е. треульгольники подобны.
Как при этом можно насчитать разные погрешности углов в (70)?
Понятно, что если треугольник меньше, то и погрешность длин у него меньше.
86 Михаил Козлов
 
08.06.12
16:23
(85) Могу прислать файл Эксель с вычислениями. Мое мыло в профиле.
87 Михаил Козлов
 
08.06.12
16:26
(66) Кстати, (56,97) - следующее неполное частное.
88 DailyLookingOn Sunset
 
08.06.12
16:27
(86)
0    0        81,9878039711
0    82        82,0000000000
71    41        81,9878039711

0    0        57,9741321625
15    56        57,9741321625
56    15        57,9827560573

82,0000000000/57,9827560573 = sqrt(2)
81,9878039711/57,9741321625 = sqrt(2)
89 Адинэснег
 
08.06.12
16:43
этож самолетик так делается. Лист пополам, потом сворачиваем уголки как самолет собираем, но углы не к центру, а в нахлест, так чтобы, нижняя часть уперлась ровно в сгиб "верхнего" уголка, а верхний уголок лег ровно на край нижнего получится 60%
Останется нихняя часть, ее обрезать
90 Deni7
 
08.06.12
16:48
Брутфорсом:
Процедура Выяснить()
   Разниццо = 1000;
   Х = 0; У = 0; ММК=0;
   
   Для МК = 0 По 100 Цикл
       Для i = 1 по 100 Цикл
           Для j = 1 по 100 Цикл
               СторонаА = Sqrt(i*i+j*j);
               i1 = МК-i;
               СторонаБ = Sqrt(i1*i1+j*j);
               
               Если СторонаА > СторонаБ Тогда
                   МаксАБ = СторонаА;
                   МинАБ = СторонаБ;
               Иначе
                   МаксАБ = СторонаБ;
                   МинАБ = СторонаА;
               КонецЕсли;
               
               Если МК > МаксАБ Тогда
                   МаксАБС = МК;
                   МинАБС = МинАБ;
               ИначеЕсли МК < МинАБ Тогда
                   МаксАБС = МаксАБ;
                   МинАБС = МК;
               Иначе
                   МаксАБС = МаксАБ;
                   МинАБС = МинАБ;
               КонецЕсли;
               
               Р = (МаксАБС - МинАБС)/МаксАБС;
               Если Разниццо > Р тогда
                   Разниццо = Р;
                   Х = i; У = j; ММК=МК;
                   СторонаАА = СторонаА;
                   СторонаББ = СторонаБ;
                   
               КонецЕсли;
           КонецЦикла;
           ОбработкаПрерыванияПользователя();
           Состояние(""+МК+" "+i);
       КонецЦикла;
   КонецЦикла;
   
   Сообщить(""+Разниццо+" "+Х+" "+У+" "+ММК);
КонецПроцедуры

Ответ: (0;0), (41;71), (82;0) Разница: 0,00014873206
(88) Да
91 Адинэснег
 
08.06.12
16:53
92 ILM
 
гуру
08.06.12
17:05
Правильно, скоро отменят интернет, выдадут всем листочки в клеточку. Циркули тоже отберут. ЕГЭ блеать!!!
93 sash-ml
 
08.06.12
18:01
почему всегда есть точка 0.0?
94 smaharbA
 
08.06.12
18:06
добавить недостающий узел внутре клетки
95 RomanYS
 
08.06.12
22:08
(70) треугольники в (51) и (66) подобны и они равнобедренные
сравнивая углы для (51) Вы взяли угол при основании, а для (66) при вершине (между равными сторонами), надеюсь не надо объяснять почему отклонение ровно в 2 раза "лучше".
Если как критерий брать абсолютную разницу, то треугольник в (66) в sqrt(2) раз лучше.
Если критерий - относительная разница или отклонение углов, то данные треугольники "равноценны".
96 GANR
 
28.06.12
19:47
Самый простой способ - составить программу

1. Выбирающую все возможные варианты треугольников с вершинами в узлах клеток из куска клетчатой бумаги 100 на 100 клеток.
2. Находящую углы треугольников из узлов (1).
3. Проверяющую максимальное отклонение углов от 60 градусов.

А именно без программы совсем никак ???
97 Михаил Козлов
 
28.06.12
20:02
(96) Перебором можно получить с трудоемкостью О(N) (N - число клеток на листе). Неполные частные - О(LOG(N)).
Для исходной задачи решение получается на 6-ом шаге.
Для числа клеток = 1000 - на 10-ом. Для 10 000 - на 13-ом.
Повторю: цель топика - обратить внимание уважаемой публики на цепные дроби, как красивый и практичный инструмент приближения чисел рациональными с небольшими знаменателями.
Что Вы имеете в виду под "без программы"? Если бы даже была явная формула через арифметические операции - это ведь тоже программа.
98 GANR
 
28.06.12
20:10
(97) "без программы" это значит алгоритм по которому человек мог-бы за разумное время (минут 20 максимум) найти решение "на бумаге".
99 Михаил Козлов
 
28.06.12
20:16
(98) Как раз неполные частные и позволяют это делать: Гюйгенс так считал число шестеренок для механической модели Солнечной системы.
Помимо эффективности вычислений, цепные дроби позволяют получить и другие интересные результаты: не поленитесь - прочитайте в Википедии.
100 NS
 
28.06.12
20:27
(99) не совсем понятно как применить их к этой задаче.
Для частных случаев - одна из сторон идет ровно горизонтально или вертикально, либо одна вершина в 0,0, а две другие в а,в и в,а - понятно, но это всего лишь частные случаи. Не факт что оптимальный треугольник будет иметь такой вид.
101 Михаил Козлов
 
29.06.12
16:54
(100) Вы правы. Я уже извинился в (69). Давайте рассматривать задачу в такой постановке. Впрочем, похоже, это условие (сторона горизонтально) не является здесь обременительным.
Замечу, что неполные частные пригодились и в исследовании чисел Фробениуса ("Цыплячьи ножки"). Еще знаю, что находили применение в квадратурных формулах для некоторых классов функций.
102 NS
 
29.06.12
16:57
(101) Где-то читал я про них в советское время. Большая статья была, или даже целая брошюра.
103 Михаил Козлов
 
29.06.12
17:15
(102) Хинчин "Цепные дроби". Не запала?
104 NS
 
29.06.12
17:21
(103) Похоже она.