На листке клетчатой бумаги 100х100 клеток разместить треугольник с вершинами в узлах, наиболее приближенный к правильному.

основание под 30градусов ???

бедняга. Задачка для 5 класса

ставишь 3 точки и соединяешь по линейке. какие сложности?

87 :)

(1)под 60

(0) рисуешь основание, измеряешь длину циркулем, делаешь 2 засечки из окончаний прямой-основания.. вроде всё..

(4) - долго описывать?
основание - 100 клеток, из середины восстанавливаем перпендикуляр и отсчитываем 87 клеток

стоп а что такое "правельный" треугольник?

кстати какой критерий "наиболее приближенный к правильному"

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

и т.д.

что есть мерило?

(5) я так понимаю без циркуля надо это сделать. По теореме синусов иил косинусов рассчитай высоту и пол стороны

блин не по теореме, а через синус или косинус угла

(5) "с вершинами в узлах"
я так понимаю вершины должны быть на пересечении разлиновки

(8) наверное не зря там про "клеточки" :)

решение можно сделать так

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

треугольник будет ТОЧНО ПРАВИЛЬНЫМ

(11) упс, по-ходу в (4) я прогнал, задачка-то с подковыркой. наверняка есть другое целое основание, при котором с целой-же высотой треугольник будет "точнее"

шесть клеток вправо три вверх в вот угол поделен на 30 и 60 грудусов

(8) минимальная разница между мин и макс стороной

+(14) к примеру основание 6, высота 4

(15) врядли )

на клетке легко сделать 60 градусов угол. Далее от него плясать.

остальные стороны будут по 5

вариант 1

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

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

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


и так далее

(19) + Либо зная длину катетов прямоугольного треугольника при углах в 60 и 30 градусов, то можно лугко получить правильный треугольник

(21) это не правильный тр-ник.

а если он неправильный, то нужно доказывать

(23) это почти правильный :) просто мне лень считать 15г через какие точки проходит

(22) + Используя торему синусов (или косинусов уже не помню) + x^2 = a^2 + b^2 Можно лугко получить длину большого катета. Малый равен 50 = (100 / 2)

(21) я так понимаю клетки должны быть целыми

(27) Ваши домыслы.

так есть же ответ уже - первая точка (0,0)
вторая - (100,0)
третья - (50,87)

(0)
A(x,y)=(0,0)
B(x,y)=(5,8.6)=(5,5*tg(3.1428/3))
C(x,y)=(10,0)

(0) Для 100
A(x,y)=(0,0)
B(x,y)=(50,86)=(50,50*tg(3.1428/3))
C(x,y)=(100,0)

(29) Точно :)

знаменитый прямоугольнфй треугольник 3-4-5 имеет погрешность от 30-60 градусов около 2%. Вполне достаточно.

Тангенс 60 (отношение высоты к половине основания ) = КОРЕНЬ(3), а это число иррациональное, поэтому совсем правильный (с вершинами в узлах) не построить.
50 и 87 - не самый лучший.

(33) не, у этого знаменитого основание = 6, а стороны=5  :)

можно конечно состваить уравнение для (16), взять производную, наэти экстремуму, но влом

(13) А зачем так? У правильного треугольника все углы по 60 градусов. Какие 30 градусов в углах?
(0) Высота у правильного треугольника составляет со сторонами угол 30 градусов. Известно также, что в прямоугольном треугольнике сторона, лежащая против угла 30 градусов, вдвое меньше гипотенузы. Соответственно, рисуем треугольник, у которого с - длина стороны, h - высота, при этом h=SQRT(3)*c/2. Если мы размещаем горизонтально основание с, и при этом оно составляет по длине целое число клеточек, то высота никак не может быть целым числом. Нетрудно видеть, что можно подобрать такое основание, при котором высота наиболее приближена к целому числу, а треугольник к правильному.

(33) Речь не о том, достаточно или нет, а о "лучшем" варианте (угол при основании наиболее близок к 60).

самый правильный, расхождения менее 0.1%

0.0
100.39
39.100

(37) ты ограничиваешь себя стороной полностью лежащей на линии, а это не обязательно

(36) Экстремум придется брать по целым точкам и можно, вернеее, точно натолкнешься на локальный экстремум. Проще в Экселе прогнать.

(40) Тогда вообще нет ограничений. Строна 100, высота вверх их середины стороны - посчитай, поставь точку и соедини. Впрочем, в (00 вроде про клетки сказано?

(41) но задача же не на такое решение в лоб ))

(39) В оптимуме 0,02%.

и вообще треугольник может быть неравнобедренным

или нет?

(44) так что в (39) решение или нет?

собственно задача найти или доказать?

Пипец правильный треугольник в (39) - две стороны по 107 и одна 86!

в екселе проганл, оптимальное

0,0
85,22
22,85

отклонениеие от идельной точки 0,000381166

(50) У меня получилось основание - 82, высота 71, отклонение -0,00034349
У другим методом такой же ответ.

де-то я слажал :))
   Для МалыйКатет = 1 по 100 Цикл
       МинимальнаяРазница = 1000;
       ИскомаяГипотенуза = МалыйКатет*2;
       Для БольшойКатет = МалыйКатет по ИскомаяГипотенуза Цикл // грубо
           Разница = Pow(ИскомаяГипотенуза,2)- Pow(БольшойКатет,2) + Pow(МалыйКатет,2);
           Если Разница < МинимальнаяРазница Тогда
               МинимальнаяРазница = Разница;
               НужныйМалыйКатет = МалыйКатет;
           КонецЕсли;    
       КонецЦикла;    
   КонецЦикла;    
   Сообщить("НужныйМалыйКатет " + НужныйМалыйКатет);

Если в школе нужен был правильный треугольник , то рисовал его так:

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

Итог: Высота 75, основание 100.

(50) И все стороны равны? Или какой там критерий?
В общем, самый равносторонний треугольник такой: чертим горизонтальный отрезок 52 , делим его пополам, откладываем от середины высоту 45 и все точки соединяем.

(51) посчитай мой треугольник, просто я не понял как ты на основании 82 получил лучший результат

апочему решили что корень из 3 нельзя построить, ведь корень из 2 можно ведь

Sin(60град) = 0.8660
т.е. высота равностороннего треугольника = 0.8660 основания.

отседова примерно следует: Если основание = 1000ед, то вершина точно будет отстоять от него точно на 866 квадратиков..
больше ничего не придумывается :)

(51) да, извиняюсь за (54) - этот самый оптимальный, между корнем из 3 и высотой всего 0.01!

а 0.8660 - корень из 2 деленное на 2

(57) +1 .

пардон, корень из 3 деленное на 2

Если критерий - минимизировать разницу межу максимальной и минимальной стороной, то это точка.

(52) Можно и программно, но в Вашем варианте число операций квадратично по числу клеток (100), а можно за LOG.

0,0
41,11
11,41

разница длин сторон составляет 0,055540132% или 0,023563682 клетки

(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  
у мну погрешность больше :)

Лучший на поле 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>

(66) в (51) погрешность меньше. А вообще - забавно, я даже возможность поворота теугольника не рассматривал... :)

(67) в (51):
-0,012196029=КОРЕНЬ(71*71+41*41)-82

(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), основываясь на неполных частных.

(68) Проверил Ваше решение: оно оказалось хуже (51) (точность чисел - 12).
У Вас тангенс угла при основании = 1,732738095238, угол = 60,009841741648
Для (51) = 1,731707317073, угол = 59,99507913
У Вас отклонение по углу = -0,009841741648
Для (51) = 0,004920871, т.е. в 2 раза меньше.

(0, 0) (41, 71) (82, 0)
отношения сторон 1,0001487 и 1

еще (0, 0) (26, 97) (97, 26) хорошо подхоит

(72) Отклонение по углу = 0,009840765720, что в 2 раза хуже (51)
(71) = (51).
Пока что (51) - лучший.
Вообще-то речь не о том, как программно получить лучшее решение. Простым перебором (трудоемкость - размер листа^2) можно найти решение.
Цель топика была обратить внимание на цепные (непрерывные) дроби, как очень эффективный (трудоемкость - логарифм от размера) инструмент в задачах, когда нужно приближать числа рациональными (с не очень большими знаменателями).
В частности, для приближения SQRT(3) с числителем и знаменателем<=100 нужное неполное частное получается на 6-м шаге.

(73) а (64) как?

(73) программно совсем не размер листа, все гораздо проще

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

то есть простой перебор с размером листа Х это примерно х*х/2 то есть половина точек, а при небольшей оптимизацией 1/8 от количества точек

(74) Отклонение по углу = 0,036721262301. В 7 раз хуже (51).

(75) Что N^2, что N^2/2, что N^2/8 - порядок N^2. А неполные частные позволяют за LOG(N).

(77) логарифмы считаются сильно дольше чем корни.

думаю, что задачу можно решать путем бинарных операций

http://s019.radikal.ru/i639/1206/4c/a988886b754e.jpg
Я вот так сделал :-)

Разместил на листке и пох что он в клетку...

(77) Не логарифмы считаются, а количество операций О(log(N)), где N - размерность задачи (число клеток). Для N = 1000 у Вас будут сотни тысяч, а в неполных частных - десятки.

(80) Извините, не понял.

(82) Сложи листок попалам вдоль, и совмести уголок с линией сгиба, отметь точку. Соедини углы с точкой.

(83) У Вас равносторонний треугольник, но вершина не попадет в узел. Речь не о том, как построить правильный треугольник - Вы, по сути воспользовались нижней стороной листа, как циркулем.

Проверил (51) и (66).
Соотношение всех сторон одинаковое и равно sqrt(2). Т.е. треульгольники подобны.
Как при этом можно насчитать разные погрешности углов в (70)?
Понятно, что если треугольник меньше, то и погрешность длин у него меньше.

(85) Могу прислать файл Эксель с вычислениями. Мое мыло в профиле.

(66) Кстати, (56,97) - следующее неполное частное.

(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)

этож самолетик так делается. Лист пополам, потом сворачиваем уголки как самолет собираем, но углы не к центру, а в нахлест, так чтобы, нижняя часть уперлась ровно в сгиб "верхнего" уголка, а верхний уголок лег ровно на край нижнего получится 60%
Останется нихняя часть, ее обрезать

Брутфорсом:
Процедура Выяснить()
   Разниццо = 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) Да

http://s019.radikal.ru/i608/1206/06/6b79cf2fcf24.jpg

Правильно, скоро отменят интернет, выдадут всем листочки в клеточку. Циркули тоже отберут. ЕГЭ блеать!!!

почему всегда есть точка 0.0?

добавить недостающий узел внутре клетки

(70) треугольники в (51) и (66) подобны и они равнобедренные
сравнивая углы для (51) Вы взяли угол при основании, а для (66) при вершине (между равными сторонами), надеюсь не надо объяснять почему отклонение ровно в 2 раза "лучше".
Если как критерий брать абсолютную разницу, то треугольник в (66) в sqrt(2) раз лучше.
Если критерий - относительная разница или отклонение углов, то данные треугольники "равноценны".

Самый простой способ - составить программу

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

А именно без программы совсем никак ???

(96) Перебором можно получить с трудоемкостью О(N) (N - число клеток на листе). Неполные частные - О(LOG(N)).
Для исходной задачи решение получается на 6-ом шаге.
Для числа клеток = 1000 - на 10-ом. Для 10 000 - на 13-ом.
Повторю: цель топика - обратить внимание уважаемой публики на цепные дроби, как красивый и практичный инструмент приближения чисел рациональными с небольшими знаменателями.
Что Вы имеете в виду под "без программы"? Если бы даже была явная формула через арифметические операции - это ведь тоже программа.

(97) "без программы" это значит алгоритм по которому человек мог-бы за разумное время (минут 20 максимум) найти решение "на бумаге".

(98) Как раз неполные частные и позволяют это делать: Гюйгенс так считал число шестеренок для механической модели Солнечной системы.
Помимо эффективности вычислений, цепные дроби позволяют получить и другие интересные результаты: не поленитесь - прочитайте в Википедии.

(99) не совсем понятно как применить их к этой задаче.
Для частных случаев - одна из сторон идет ровно горизонтально или вертикально, либо одна вершина в 0,0, а две другие в а,в и в,а - понятно, но это всего лишь частные случаи. Не факт что оптимальный треугольник будет иметь такой вид.

(100) Вы правы. Я уже извинился в (69). Давайте рассматривать задачу в такой постановке. Впрочем, похоже, это условие (сторона горизонтально) не является здесь обременительным.
Замечу, что неполные частные пригодились и в исследовании чисел Фробениуса ("Цыплячьи ножки"). Еще знаю, что находили применение в квадратурных формулах для некоторых классов функций.

(101) Где-то читал я про них в советское время. Большая статья была, или даже целая брошюра.

(102) Хинчин "Цепные дроби". Не запала?

(103) Похоже она.