Правильный треугольник на клетчатой бумаге #614348

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

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

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

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

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

87 :)

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

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

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

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

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

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

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

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

решение можно сделать так из угла под проводим 2 линии под улами 15 и 75 градусов, на этих линиях ищим точку где она пересечет центр клеточки (а она гарантировано пересекает, вроде 1/8 клеткам, или 16), дальше соеденяем. треугольник будет ТОЧНО ПРАВИЛЬНЫМ

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

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

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

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

врядли )

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

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

вариант 1 первая точка 0.0 вторая точка 4.1 третья точка 1.4 ----------------------------- вариант 2 первая точка 0.0 вторая точка 8.2 третья точка 2.8 и так далее

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

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

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

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

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

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

Ваши домыслы.

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

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

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

Точно :)

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

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

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

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

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

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

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

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

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

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

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

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

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

или нет?

так что в решение или нет?

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

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

в екселе проганл, оптимальное 0,0 85,22 22,85 отклонениеие от идельной точки 0,000381166

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

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

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

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

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

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

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

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

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

+1 .

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

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

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

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

не, там слажал, потом малехо поправил, но все-равно более верный результат в не получил    МинимальнаяРазница = 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/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>

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

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

Не проверял, скорее всего Вы правы. Я как-то заложился на горизонтальное основание - виноват. В этом случае задача сводится к поиску целых p и q (p<=100, q<=50), так что p/q наилучшим образом приближает SQRT. По этой теме есть интересный аппарат цепных дробей (, который позволяет очень быстро находить такие числа. Советую почитать, особенно приложения. В частности, для ПИ: 3, 22/7, 333/106, 355/113, 103993/33102. Значением 22/7 часто пользовались греки (архимедово приближение). Гюйгенс, когда делал механическую модель солнечной системы, тоже их использовал. Первый пример трансцендетного числа привел Лиувилль (году этак в 1841), основываясь на неполных частных.

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

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

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

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

а как?

программно совсем не размер листа, все гораздо проще первая точка всегда 0.0 вторая точка лежит в сегменте 15градусов от точки 0.0 третья точка определяется как одна из 4х то есть простой перебор с размером листа Х это примерно х*х/2 то есть половина точек, а при небольшей оптимизацией 1/8 от количества точек

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

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

логарифмы считаются сильно дольше чем корни. думаю, что задачу можно решать путем бинарных операций

Я вот так сделал :-)

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

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

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

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

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

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

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

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

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 81,9878039711/57,9741321625 = sqrt

этож самолетик так делается. Лист пополам, потом сворачиваем уголки как самолет собираем, но углы не к центру, а в нахлест, так чтобы, нижняя часть уперлась ровно в сгиб "верхнего" уголка, а верхний уголок лег ровно на край нижнего получится 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 Да

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

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

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

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

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

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

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