1

Тема: OFF: Прошу подключиться к решению загадки… — II

В блоге Олега Кляйна (Helge Klein) попалось интересное задание Quickest Way to Create Text File of Specific Length:

How to Create Such a Beast

That was the question I asked myself. I was not thrilled by the prospect of copying and pasting blocks of text in an editor until the required length had been reached.

Perl
Luckily I remembered that Perl has a function that makes such a task trivial: the ‘x’ operator. Here is what I came up with:

perl -e "print '1' x 32739" > 32739.txt

If you have Perl installed, that line can be executed from the regular Windows command line. “Perl -e” executes one command string (enclosed in double quotes). The result is then written to the file 32739.txt with the command line’s output redirection operator “>”.

Alternatives?

Are there any other elegant ways to create a text file with one line of exactly 32,739 characters? If you know of one, please let me know by commenting below.

Условно говоря, каким образом можно быстро и просто создать текстовый файл заданной длины?

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

AlexII пишет:

Simple, but long-time command for NT-based command processor:

>nul copy nul 32739.txt & for /l %i in (1, 1, 32739) do @(<nul set /p SomeVar=1)>>32739.txt

The brackets need only for prevent redirection in this case (as … 1>>file.txt).

This way is more easy and quickly:

(for /l %i in (1, 1, 32739) do @<nul set /p SomeVar=1)>32739.txt

Но, зараза, движок блога скушал мой код . Так что, помещаю его здесь.

P.S. Перед тем как перейти по ссылке выше и посмотреть изложенные варианты, попробуйте сами .

2

Re: OFF: Прошу подключиться к решению загадки… — II

Через JS, но как-то многовато кода

CMD @ECHO OFF & MSHTA "javascript:s=new ActiveXObject('Scripting.FileSystemObject').
GetStandardStream(1); for(i=0;i<32739;i++)s.Write(1);close();" 1 | MORE >> 32739.txt

3

Re: OFF: Прошу подключиться к решению загадки… — II

JSman пишет:

Через JS, но как-то многовато кода

cmd /c mshta "javascript:new ActiveXObject('Scripting.FileSystemObject').
GetStandardStream(1).Write(new Array(32769+1).join(1));close()" 1 > 32769.txt

Создание строки заданной длины через создание массива. Так наверно будет покомпактнее и чуть побыстрее.

( 2 * b ) || ! ( 2 * b )

4

Re: OFF: Прошу подключиться к решению загадки… — II

Одна строчка

CreateObject("Scripting.FileSystemObject").OpenTextFile("Out.txt", 2, True).Write String(32444," ")
Времени не хватает... :-(

5 (изменено: is5157, 2011-12-15 08:56:36)

Re: OFF: Прошу подключиться к решению загадки… — II

Можно так: fsutil file createnew [путь к создаваемому файлу] [размер в байтах]. Например: fsutil file createnew D:\test.txt 1000. После выполнения данной команды на диске "D" создастся файл "test.txt" размером 1000 байт (справедливо для Win2K, XP, Vista, 7).

6

Re: OFF: Прошу подключиться к решению загадки… — II

is5157 пишет:

(справедливо для Win2K, XP, Vista, 7)

Неа … Справедливо для файловой системы NTFS и при наличии у пользователя административных привилегий.

7 (изменено: kaster, 2011-12-15 09:46:25)

Re: OFF: Прошу подключиться к решению загадки… — II

alexii, разве? msdn говорит, что утилита прекрасно работает и в FAT. Да и для записи на диск нужны привелегии записи на диск, зачем же полные административные права?

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

8

Re: OFF: Прошу подключиться к решению загадки… — II

kaster пишет:

alexii, разве? msdn говорит, что утилита прекрасно работает и в FAT.

Проверил. Беру свои слова обратно. Я спутал с другой командой.

kaster пишет:

Да и для записи на диск нужны привелегии записи на диск, зачем же полные административные права?

Для запуска «fsutil.exe».

9

Re: OFF: Прошу подключиться к решению загадки… — II

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

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

10 (изменено: stir, 2011-12-16 11:14:12)

Re: OFF: Прошу подключиться к решению загадки… — II

ОФФ: А автор точно мужского рода.. а то тут вспомнил малость немецкий.. в переводе близко слышится что-то вроде - Маленькая Ольга тчк ком, . На фото мужчина - спору нет.. Пошлепал по клавишам нашел.. имя женское распространилось и набирает обороты" для именования мужчин в европе в настоящее время, малость претерпев изменение - с буквы А на Е в конце имени, тем самым став мужским.. интересные тенденции в мире, наши берут их имена, а они у нас.. Просто там ранее Ольг было очень много и мало Олегов (в пер. СВЯТАЯ/СВЯТОЙ), http://kurufin.narod.ru/html/Translate/olga.html. Изучая не один год немецкий я ни разу не слышал и не прочитал газет немецких с мужским именем ХЕЛЬГ, попадались только женские имена - Хельга. Вообщем борьба полов закончилась равенством полным... .
Извините, что не по теме.

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

Любители построили Ковчег, а профессионалы - Титаник.

11

Re: OFF: Прошу подключиться к решению загадки… — II

Предлагаю не забрасывать тему задач и заодно следующую игру/задачу: программа генерирует массив из десяти случайных двухбайтовых беззнаковых целых чисел, затем эти числа начинает вам выдавать по одному. Ваша задача- остановиться на самом большом числе в массиве(если таких несколько, то на любом из них). Вопросы:
1) какова оптимальная стратегия игры?
2) каковы шансы на победу при следовании оптимальной стратегии?
3) рассмотреть более общие случаи(массив из n чисел, диапазон от нуля до m).
Естественно случайные числа считать абсолютно случайными .

12 (изменено: BatLife, 2012-05-16 17:14:49)

Re: OFF: Прошу подключиться к решению загадки… — II

Александр_ пишет:

Предлагаю не забрасывать тему задач и заодно следующую игру/задачу: программа генерирует массив из десяти случайных двухбайтовых беззнаковых целых чисел, затем эти числа начинает вам выдавать по одному. Ваша задача- остановиться на самом большом числе в массиве(если таких несколько, то на любом из них). Вопросы:
1) какова оптимальная стратегия игры?
2) каковы шансы на победу при следовании оптимальной стратегии?
3) рассмотреть более общие случаи(массив из n чисел, диапазон от нуля до m).
Естественно случайные числа считать абсолютно случайными .

Возможно и имеются какие-то несущественные отличия, но в целом подобная задача похожа на так называемую "Задачу о разборчивой невесте", про которую можно найти немало информации в интернете

Конечно в общем случае решние может зависеть от распределения, однако в конкретном случае, когда подразумевается равномерное распределение, ответом вроде бы является следующий: пропустить первые n/3 чисел, и потом выбрать первое из самых больших чисел

Задача о разборчивой невесте, или проблема остановки выбора может быть сформулирована следующим образом:[1]

1.Невеста ищет себе жениха (существует единственное вакантное место).
2.Есть известное число n претендентов.
3.Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
4.О каждом текущем претенденте известно, лучше он или хуже любого из предыдущих.
5.В результате общения с текущим претендентом невеста должна ему отказать либо принять его предложение. Если предложение принято, процесс останавливается.
6.Цель: выбрать лучшего претендента.
Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность. А именно: если число кандидатов достаточно велико (порядка сотни), оптимальная стратегия будет заключаться в отклонении всех первых n/e (где e — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих.[2] При увеличении n, вероятность выбора наилучшего претендента стремится к 1/e, то есть примерно к 37%

13 (изменено: Александр_, 2012-05-16 17:45:17)

Re: OFF: Прошу подключиться к решению загадки… — II

BatLife, да это очень похожая задача. Но тут есть очень большое отличие- у нас есть информация о выпадающих числах(двухбайтовое целое- т.е. от нуля до http://ru.numberempire.com/equation.render?2^{16}-1). Т.е. если нам первым выпадет число 65535, то приняв его мы гарантированно побеждаем. Поэтому стратегия должна быть немного изменена и вероятность выигрыша тоже вырастет. Кстати цифры можно получать/проверять эмпирически, условие специально под это подогнано .

14

Re: OFF: Прошу подключиться к решению загадки… — II

Александр_ пишет:

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

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

15

Re: OFF: Прошу подключиться к решению загадки… — II

Poltergeyst, вы не так поняли условие. Попробую объяснить на примере:
1) Программа генерирует массив, например {123, 10, 54, 96, 340, 345, 960, 343, 234, 0}.
2) Программа выдаёт вам первое число- 123, остальные вы не знаете, но должны решить является ли это число наибольшим во всём массиве. Если вы говорите "да", то проигрываете, поскольку далее есть числа больше, если "нет", то...
3) Программа выдаёт вам следующее число- 10. Тут вы должны сделать тот же выбор, что и на предыдущем шаге, т.е. решить является ли число 10 наибольшим в массиве(число 123 уже отвергнуто, его уже нельзя будет выбрать). Тут явно придётся ответить "нет", ведь 123>10.
4) Далее программа выдаёт число 54, оно отвергается по той же причине.
5) Программа выдаёт число 96, оно отвергается по той же причине.
6) Наконец программа выдаёт число 340 и вы должны решить, стоит ли на нём останавливаться или дальше есть число больше.
И так продолжается до тех пор пока вы не откроете последнее число в массиве или не перестанете открывать числа, объявив последнее открытое наибольшим.
Надеюсь так понятно, если нет, то пишите- я сделаю программную реализацию.

16

Re: OFF: Прошу подключиться к решению загадки… — II

Простенькая задача, даже стыдно.
Есть командный файл вида:

@echo off
if "%~1"=="" goto NoArgs
echo Делаем что-то полезное
pause>nul
exit /b

:NoArgs
echo Не указаны аргументы!!!
pause>nul
exit /b

:BackDoor
echo Призошёл переход на :BackDoor
pause>nul

(вначале проверяем, заданы ли аргументы: если заданы, то что-то с ними делаем; если нет — выводим предупреждение об этом).
Требуется запустить командный файл таким образом, чтобы выполнились строки, следующие за меткой BackDoor.

17 (изменено: wisgest, 2012-11-20 02:30:26)

Re: OFF: Прошу подключиться к решению загадки… — II

Задача может показаться не имеющей никакого применения, может это и так, но не совсем.

Допустим, в командном файле есть подпрограмма :SUB
Можно сделать перенаправление её вывода

call :SUB > file.txt

но нельзя

call :SUB | program.exe

точно так же как нельзя обработать её вывод

for /f %%i in ('call :SUB') do ...

— в обоих случаях будет ошибка

Недопустимая попытка перехода на метку пакетного файла извне этого файла.

т.к. в обоих случаях для выполнения внутренних команд CMD.EXE создаётся его новый процесс (в последнем случае и для не внутренних).

Возникает задача вызвать командный файл из самого себя с некоторой метки (если не выносить подпрограмму в отдельный файл). Можно, конечно, вызывать файл с каким-либо ключом, и если этот ключ обнаружен, передавать управление на заданную метку; можно в начало командного файла добавить префикс, позволяющий запускать командный файл с любой метки, приблизительно так (первым аргументом может быть начинающаяся с двоеточия метка):

set "label=%~1"
if %label:~0,1%==: shift /1 & goto %label%

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


Это была лишь мотивация, если же нужна подсказка, то попробуйте в #16 включить ECHO ON… Хотя, скорее всего, задача действительно слишком простая.

18 (изменено: Rumata, 2012-11-20 09:07:38)

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest пишет:

Задача может показаться не имеющей никакого применения

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

wisgest пишет:

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

Либо что-то не договариваете, либо темните.

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


call "%~n0" :label другие параметры
( 2 * b ) || ! ( 2 * b )

19

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:
wisgest пишет:

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

Либо что-то не договариваете, либо темните.

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

#16.bat Трам-пам-пам

— Спрашивается: что должно быть на месте «Трам-пам-пам»?
Ответ достижим путём логических рассуждений (и некоторого опыта работы с командными файлами), никаких пасхальных яиц и рождественских кроликов.

20

Re: OFF: Прошу подключиться к решению загадки… — II

Поскольку тут спойлера нет, я на почту свой вариант послал.

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

21

Re: OFF: Прошу подключиться к решению загадки… — II

Spy00000, всё верно!

22

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:

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

call "%~n0" :label другие параметры

Да, вероятно, неплохое. Правда, я ещё не определился с его окончательным вариантом: например, делать SETLOCAL перед этим префиксом или после…

CALL здесь на самом деле ненужно, т.к. перенаправление

"%~0" :метка другие параметры|program.exe

в действительности выполняется как

%ComSpec% /S /D /c" "%~0" :метка другие параметры"|program.exe

что и так обеспечивает возврат в командный файл после завершения вспомогательного процесса CMD.EXE, а также делает ненужными в вызываемой таким образом подпрограмме SETLOCAL и ENDLOCAL.
Я даже думаю, что для полного контроля в таком вызове лучше явно указывать CMD.EXE с необходимыми ключами, например, /V для ENABLEDELAYEDEXPANSION.

Более того, CALL, может быть, даже вредно, т.к. порождает проблему удвоения символа «^» при заключении его в кавычки:

call echo "Hello^world"

23 (изменено: wisgest, 2014-01-08 19:18:05)

Re: OFF: Прошу подключиться к решению загадки… — II

Решение предложенной в #16 задачи зиждется на
1) принципе

Smitis пишет:

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

— это в полной мере относится не только к переменным среды (без отложенной подстановки), но и к параметрам командного файла (и, вероятно, к переменным цикла); настоящими переменными можно считать лишь переменные среды при их отложенной подстановке (и при использовании без обрамляющих «%» или «!» в арифметических операциях SET /A — в этом случае их подстановка ещё более отложенная);
2) принципе стандартного разделения командной строки на параметры.

***
Возможный ответ:

#16.bat -"=="-" goto BackDoor "

с передачей параметров:

Spy00000 пишет:
16.bat '"=="'" shift && goto BackDoor " 1 2 3

***
___________________

P.S. Из рассмотренной задачи вытекает обратная:
получить в общем случае параметры командного файла (в переменную среды, для возможности использования с отложенной подстановкой) без потерь и инъекций кода.

Этот вопрос на первый взгляд может показаться на порядок проще предыдущего (а при повторном взгляде — сложиться мнение, что язык командных файлов — наспех сколоченная недоделка), но, по-моему, всё наоборот. По крайней мере, решение полученное мною невозможно записать в одну строку.
Пожалуй, для этого вопроса лучше создать отдельную тему в разделе отведённом командным файлам.
(08.01.2014: Отдельной темы, по-видимому, уже не создам. Кратко об этом решении можно прочесть в http://forum.script-coding.com/viewtopi … 980#p78980.)

24

Re: OFF: Прошу подключиться к решению загадки… — II

Ага! Я думал в том же направлении, но "магический" аргумент пытался целиком обрамить кавычками. В результате не получалось - либо кавычки лишние, либо строка не подставлялась. Я думал, что составные параметры надо полностью обрамлять по краям в кавычки. Оказывается - не обязательно.

( 2 * b ) || ! ( 2 * b )

25

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest пишет:

получить в общем случае параметры командного файла (в переменную среды, для возможности использования с отложенной подстановкой) без потерь и инъекций кода

Занимался этой проблемой именно в таком ключе, когда писал WSH интерпретатор. Здесь есть проблемы с такими символами как ^ (карет, циркумфлекс), " (кавычки), ! (восклицательный знак). С ними полная путаница - одни надо экранировать, другие не надо. Причем экранирование у каждого символа свое - кавычки удваиваются; воскл.знак надо предварять циркумфлексом. А последний не надо, но чтобы его надежно передать, надо его "завернуть" в кавычки.

( 2 * b ) || ! ( 2 * b )

26

Re: OFF: Прошу подключиться к решению загадки… — II

Первый пост:

alexii пишет:

Условно говоря, каким образом можно быстро и просто создать текстовый файл заданной длины?

С файлами нулевой длинны особых сложностей нет, верно?

$ cd.>null.txt

На счет определенной длинны... На ум приходит только fsutil с возможностью создания разреженных файлов:

$ fsutil file createnew file.txt 32739

Но это не совсем то, так как по факту размер файла на диске будет всего о нескольких (кило)байт. Не уверен, что задача как-то решаема без забивания создаваемого файла некими данными (в случае с hex'ом достаточно забить нулями); по логике же цель задачи как таковой и вовсе неясна: в быту таким блудом вряд ли имеет смысл заниматься. А вот ограничение размера файла задача вполне насущная (но и решаемая просто), ибо вряд ли имеет смысл, например, отдавать под логи сотни мегабайт.

27

Re: OFF: Прошу подключиться к решению загадки… — II

greg zakharov пишет:

в быту таким блудом вряд ли имеет смысл заниматься

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

greg zakharov пишет:

размер файла на диске будет всего о нескольких (кило)байт

Сколько укажете:

U:\>fsutil file createnew null.txt 1000000000 && dir null.txt
File U:\null.txt is created
 Volume in drive U is PC COE
 Volume Serial Number is EC48-A9DB

 Directory of U:\

22.11.2012  18:57     1 000 000 000 null.txt
               1 File(s)  1 000 000 000 bytes
               0 Dir(s)  84 080 013 312 bytes free
( 2 * b ) || ! ( 2 * b )

28

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:

Сколько укажете:...

Все верно. Речь ведь была о создании разреженного файла, а значит нужно использовать ключ sparse, в противном случае мы просто получаем "болванку" для такового файла. В итоге:

$ fsutil file createnew null.txt 5000000
$ fsutil sparse setflag null.txt
$ fsutil sparse setrange null.txt 0 5000000

Как-то так, точно не помню. fsutil'ьей пользовался лишь раз пять.

29

Re: OFF: Прошу подключиться к решению загадки… — II

Задачка из геометрии: как вычислить число Пи?
Да, если Вы сразу полезли в справочник, то не выкладывайте здесь готовый ответ.

30

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Задачка из геометрии: как вычислить число Пи?

Площадь единичного круга:

2*int(sqrt(1-x^2),x=-1..1);

31

Re: OFF: Прошу подключиться к решению загадки… — II

Другой вариант - площадь n-угольника. Чем больше n, тем точнее.

32

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Другой вариант - площадь n-угольника. Чем больше n, тем точнее.

Площадь правильного n-угольника, вписанного в окружность единичного радиуса:

(1/2)*n*sin(2*Pi/n)

или описанного:

n*tan(Pi/n)

Замечаете подвох?! Сможете его обойти?

33 (изменено: kaster, 2012-12-09 13:52:07)

Re: OFF: Прошу подключиться к решению загадки… — II

Очевидно, если использовать компьютер для вычисления пи, то надо использовать ряды. Простейшие, которые приходят мне на ум, это разложение в ряд Тейлора некоторых обратных тригонометрических функций, типа arcctg(x) или arccos(x).

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

34

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest пишет:

Площадь правильного n-угольника, вписанного в окружность единичного радиуса:

(1/2)*n*sin(2*Pi/n)

или описанного:

n*tan(Pi/n)

Замечаете подвох?! Сможете его обойти?

Зачем выражать площадь через Пи?
Я имел в виду площадь правильного n-угольника, вписанного в окружность единичного диаметра (или радиуса).

35

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Я имел в виду площадь правильного n-угольника, вписанного в окружность единичного диаметра (или радиуса).

Я догадался (радиуса, конечно).

ypppu пишет:

Зачем выражать площадь через Пи?

Что получилось, то получилось.

Разбиваем многоугольник на n равных треугольников, одна из вершин каждого из которых — центр n-угольника (а две остальные — соседние вершины n-угольника).
Две стороны треугольника равны 1 как радиусы, угол между ними (тот, который с вершиной в центре n-угольника) — 2*Pi/n.
Площадь одного треугольника (по двум сторонам и углу между ними) — 1/2*sin(2*Pi/n),
их общая площадь — 1/2*n*sin(2*Pi/n)

Имелись другие соображения по вычислению площади аппроксимирующего n-угольника?
Нет? — Задача не решена.

wisgest пишет:

Замечаете подвох?! Сможете его обойти?

Я могу.

36 (изменено: ypppu, 2012-12-09 19:43:39)

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest пишет:

Площадь правильного n-угольника, вписанного в окружность единичного радиуса:

(1/2)*n*sin(2*Pi/n)

или описанного:

n*tan(Pi/n)

Сходу не сообразил, что в Вашем примере Pi=180°, а не Pi=3,14.


wisgest пишет:

Имелись другие соображения по вычислению площади аппроксимирующего n-угольника?
Нет? — Задача не решена.

wisgest пишет:

Замечаете подвох?! Сможете его обойти?

Я могу.

Поздравляю, я не увидел подвох.
Добавлено: Хотя может возникнуть мысль, что sin(2*Pi/n)=2tg(Pi/n). Но это может быть только при ооочень большом числе углов, да то приблизительно.

37 (изменено: kaster, 2012-12-09 23:46:54)

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Хотя может возникнуть мысль, что sin(2*Pi/n)=2tg(Pi/n)

Ну да, или если переиначить sin(a) ~ a при малых а, а именно такие а и надо рассматривать для аппроксимации.

ypppu пишет:

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

Ты хотел аппроксимировать круг квадратом? Тогда да, Pi = 2.

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

38 (изменено: wisgest, 2012-12-10 06:55:16)

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Сходу не сообразил, что в Вашем примере Pi=180°, а не Pi=3,14

А что такое 180°? как посчитать sin(x°), не полагая 180°=3.14…?
Я никого не хотел запутать обозначениями. И пример не совсем мой. Я лишь показал, с чем можно столкнуться, пойдя в направлении, в котором Вы послали, хотя сами, возможно, не ходили.
Но и на этом пути есть выход…


Добавлено. В общем, и в левой и в правой частях равенства

limit(1/2*n*sin(2*Pi/n), n = infinity) = Pi

стоит одно и то же неизвестное Pi, и нельзя подставить его в левую часть под sin(), чтобы вычислить правую. Нужны дополнительные рассуждения.

39

Re: OFF: Прошу подключиться к решению загадки… — II

Ну да, искать число Пи через синус - нет практического смысла. Разве что на калькуляторе сломалась кнопка с числом Пи.

40 (изменено: wisgest, 2012-12-12 02:57:09)

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Ну да, искать число Пи через синус - нет практического смысла. Разве что на калькуляторе сломалась кнопка с числом Пи.

Если на калькуляторе сломалась кнопка с числом Пи (подозреваю, что вопрос возник всвязи с отсутствием в AutoHotkey встроенной константы), то быстрее и точнее будет 2*arcsin(1), 2*arccos(0) или 4*arctg(1) — kaster совершенно справедливо написал:

Очевидно, если использовать компьютер для вычисления пи, то надо использовать ряды. Простейшие, которые приходят мне на ум, это разложение в ряд Тейлора некоторых обратных тригонометрических функций, типа arcctg(x) или arccos(x).

Тем не менее, насколько я знаю, исторически число Пи искали именно через площадь (или всё-таки периметр) аппроксимирующего многоугольника. Поэтому хотелось бы пройти этот путь до конца.

Если кратко (а можно было бы и растечься мыслию по древу), то необязательно рассматривать все значения n — предел сходящейся последовательности равен пределу любой её подпоследовательности. Начнём с квадрата — в этом случае нам надо знать синус прямого угла и мы его знаем. На каждом следующем шаге будем увеличивать число сторон не на 1, а в 2 раза, угол при этом будет уменьшаться в 2 раза и для вычисления его синуса можно воспользоваться формулой

sin(x/2) = sqrt((1 - sqrt(1 - sin(x)^2)) / 2)

41

Re: OFF: Прошу подключиться к решению загадки… — II

Мне кажется, использовать тригонометрические функции для выведения числа ПИ как-то неправильно(есть ощущение нарушения причинно-следственной связи). Но как и древние, думаю плясать придётся от площади. Только считать её немного иначе .

Есть формула окружности: R^2 = X^2 + Y^2.
Раз есть формула, никто не мешает воспользоваться численными методами:


Option Explicit
Const R = 5 
Const itTrh = 7 ' требуемая погрешность(знаков после запятой)
' 1. численно вычисляем площадь круга
' 2. S=pi*R^2 => pi = S/R^2 , сверяемся со значением на предыдущем шаге. 
' Если "грубовато", уменьшаем dX и считаем заново

Dim itStep
itStep = R * 0.1 ' начальный шаг вычисления(надо же с чего-то начинать :))

Dim X, prevX, S, PI, prevPI, work
work = True
Do
  ' считаем площадь(численное интегрирование)
  wscript.echo "число шагов интегрирования: " & 2 * R / itStep
  For X = -R To R step itStep
    S = S + 0.5*(Y(X) + Y(prevX))*(X - prevX)
    prevX = X
  Next
  PI = 2 * S / R^2
  If prevPI <> 0 Then
    If ABS(PI - prevPI) < 10^(-itTrh) Then work = False
  End If
  prevPI = PI
  wscript.echo "S = " & S
  S = 0
  itStep = itStep / 2
  wscript.echo "pi = " & prevPI
  wscript.echo "__________________________"
Loop While work

Function y(x)
  y = (R^2 - x^2)^0.5
End Function

Что характерно, при R=1 я так и не дождался заветных 3.1415926(при примерно 42 млн. шагов прибил скрипт). При большем значении радиуса первые семь знаков получаются достаточно быстро. При радиусе 10(и Const itTrh = 10) на 21 млн. шагов(на моём ноуте примерно три с половиной минуты) получаем 10 знаков после запятой:
pi = 3.14159265355507(каноничные значения выделил жирным).

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

42

Re: OFF: Прошу подключиться к решению загадки… — II

P.P.S. это конечно не совсем геометрическое решение, но ничего умнее вписанных/описанных многогранников наверное всё равно не придумать.

Тут мысленно представил графически то что я сделал - по сути я таки вписывал в окружность многогранники, правда не равносторонние .

43 (изменено: kaster, 2012-12-13 01:18:38)

Re: OFF: Прошу подключиться к решению загадки… — II

BeS Yara пишет:

есть ощущение нарушения причинно-следственной связи

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

BeS Yara пишет:

Но как и древние, думаю плясать придётся от площади

Те, что не такие древние, плясали все же от рядов.
Например Виет
http://upload.wikimedia.org/math/2/1/2/212ca490e5d7bf6c1c58b0ad64e40afa.png
или ряд предложенный индийским самородком Рамануджаном
http://upload.wikimedia.org/math/c/a/a/caaf05280ec5e0465b648f2e570f1c0a.png
кстати говоря получен как раз таки разложением арктангенса в ряд Тейлора.
Или вот еще, суперсходящийся ряд предложенный братьями Чудновскими
http://upload.wikimedia.org/math/b/b/1/bb1658a0185ff273d8a1a79611d7b470.png
За каждую итерацию он дает 14 верных знаков после запятой, невиданная для того времени точность. А ты говоришь про миллионы итерации на 7 знаков

BeS Yara пишет:

но ничего умнее вписанных/описанных многогранников наверное всё равно не придумать


BeS Yara пишет:

Тут мысленно представил графически то что я сделал - по сути я таки вписывал в окружность многогранники, правда не равносторонние

Многогранники это трехмерные объекты. Возможно, ты имел в виду многоугольники. То что ты написал, конечно верно. Но ты попросту провел численное интегрирование методом прямоугольников. Кстати, если использовать метод трапеций, то ты можешь повысить точность интегрирования на порядок.

Update
А нет, вру, ты и так использовал метод трапеций

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

44

Re: OFF: Прошу подключиться к решению загадки… — II

kaster пишет:

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

Я в другом смысле - в силу тематики форума, большинство задачек-загадок я рассматриваю в плоскости скриптов. Поэтому завызываясь на тригонометрические функции можно просто сказать что pi = 4 * Atn(1) (пример из хэлпа). Или вообще влоб: pi = Math.PI.

К тому-же, я слабо представляю перевод синуса угла в угол математически.

kaster пишет:

Те, что не такие древние, плясали все же от рядов.

Да, я заглядывал в вики . Правда для чистоты эксперимента я начал с тригонометрии(освежить школьные знания). Когда упёрся в полученную мной на основании тригонометрии зависимость:
F(pi,n) = Cos(pi/n)-1/Cos(pi/n) = 0
и посмотрел на прикольный график(от pi/n), понял что тут ловить особо нечего(функция, что логично, вышла периодическая и знакопеременная).

Уже потом глянул статью про пи(особенно порадовала история с билем про ПИ=3.2). Чтобы использовать ряды для решения этой задачи, нужно понимать их смысл(иначе это читерство ). Так как матан из головы давно повыдуло, воспользовался численными методами. Тем более, что кроме объёма вычислений, матиматика там используется базовая. Может потому и запало в память, имхо, самый ценный предмет, связанный с матиматикой, с учёбы в ВУЗе. Правда сверх метода трапеции для интергирования и дихотомии для уравнений я уже ничего оттуда не помню .

В обиходе я редко использую больше 4-7 знаков после запятой(для пи), для бытовых задач часто хватает и двух. А их запомнить не проблема(не будем вспоминать китайцев-мнемонистов).

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

45

Re: OFF: Прошу подключиться к решению загадки… — II

Имелось в виду немного другое. Но в любом случае, скрипт так скрипт
Ряд Виета


#!/usr/bin/python2.7
import math
a_old = 0.5*2**0.5;
n = 1
tmp = a_old
while True:
    a = 0.5*(2+2*a_old)**0.5;
    tmp *= a
    print '%i interation:\t%.15f' % (n, 2/tmp - math.pi)
    n += 1
    a_old = a
    raw_input()

Точность до 15 знака после запятой достигается за 24 итерации.
Или вот, ряд Брента-Саламина позволяет получать число пи ограниченное лишь машинной точностью за 3 итерации


#!/usr/bin/python2.7
import math
a_old = 1.0; b_old = 1.0/2**0.5; t_old = 0.25; p_old = 1.0
n = 1
while True:
    a = 0.5*(a_old + b_old)
    b = (a_old*b_old)**0.5
    t = t_old - p_old*(a_old - a)**2
    p = 2*p_old
    print '%i iteration:\t%.17f\t%.17f' % (n, (a + b)**2/(4*t), math.pi)
    raw_input()
    n += 1
    a_old = a; b_old = b; t_old = t; p_old = p
autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

46

Re: OFF: Прошу подключиться к решению загадки… — II

Оказывается, на autohotkey.com тоже поднималась эта тема.

47

Re: OFF: Прошу подключиться к решению загадки… — II

kaster пишет:

Имелось в виду немного другое. Но в любом случае, скрипт так скрипт
Ряд Виета

Лучше взять разложение в ряд формулы Мэчина (из той же википедии)

( 2 * b ) || ! ( 2 * b )

48 (изменено: kaster, 2012-12-14 00:35:18)

Re: OFF: Прошу подключиться к решению загадки… — II

Вот еще один способ основанный на методе Монте-Карло. При количестве испытаний за несколько миллионов дает точность до 3-4 знаков после запятой.


#!/usr/bin/python2.7
from math import pi
from random import random as rnd, randint as rndint
total = 0.0
success = 0.0
n = 1
while True:
    x = rnd()
    y = rnd()
    if x**2+y**2 <= 1.0:
        success += 1.0
    total += 1.0
    pi_num = 4*success/total
    if n % 1000000 == 0:
        print '%i dots:\t%.15f\t%.15f' % (n, pi_num, pi)
    n += 1
Rumata пишет:

Лучше взять разложение в ряд формулы Мэчина

Ну точно хуже Брента-Саламина, но получше чем Виета, 15 знаков за 10 итераций


#!/usr/bin/python2.7
from math import pi
al1 = 1.0/5.0
al2 = 1.0/239.0
pi_num = 0.0;
n = 1;
while True:
    pi_num += 4*(4*(-1)**(n+1)*al1**(2*n-1)/(2*n-1) - (-1)**(n+1)*al2**(2*n-1)/(2*n-1))
    print '%i iteration:\t%.15f\t%.15f' % (n, pi_num, pi)
    n += 1
    raw_input()
autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

49

Re: OFF: Прошу подключиться к решению загадки… — II

разложение в ряд формулы Мэчина
Ну точно хуже Брента-Саламина, но получше чем Виета, 15 знаков за 10 итераций

Таки да...

Если бы в JS не было встроенной константы Math.PI, то ее можно было бы вычислить, например, так (3 итерации, погрешность в 16 знаке)


var PI = (function()
{
    var EPS = 1e-5;

    var a = 1;
    var b = 1 / Math.sqrt(2);
    var t = 1 / 4;
    var p = 1;
    var an, bn, PI;

    while ( true ) {
        PI = (a + b) * (a + b) / (4 * t);

        var an = (a + b) / 2;
        var bn = Math.sqrt(a * b);

        if ( Math.abs(an - a) <= EPS || Math.abs(bn - b) <= EPS ) {
            break;
        }

        t = t - p * (a - an) * (a - an);
        p = 2 * p;
        a = an;
        b = bn;
    }

    return function()
    {
        return PI;
    };
})();
( 2 * b ) || ! ( 2 * b )

50

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata, да, я уже приводил Брента-Саламина выше, только на питоне Только там погрешность это на самом деле не погрешность, а нехватка точности. В питоне, полагаю на других ЯП тоже, double может точно хранить только 16 знаков после запятой, не говоря уже про погрешности округления.

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

51 (изменено: Rumata, 2012-12-14 04:53:15)

Re: OFF: Прошу подключиться к решению загадки… — II

kaster пишет:

я уже приводил Брента-Саламина выше, только на питоне

Ага. Видел (= Полагаю, что в случае отсутствия такой константы в питоне была бы реализована соответствующая функция, полагаю, что питоноводы реализовали бы ее так, чтобы она кешировала свой результат для повторного использования.

====

Кстати. При разложении арктангенса в ряд Тейлора получается "знакопеременная" последовательность (не помню точное название таких рядов). Общий их вид таков:


F(x) = f0(x) - f1(x) + f2(x) - f3(x) + ...

где fi(x) - некоторая функция, чаще степенная с некоторым множителем.

Предлагаю поиздеваться над очень простой задачей - максимально упростить вычисление перемены знака у следующего члена ряда в общем случае и для арктангенса - в частном случае, как пример с дробным множителем:


arctg x = x - x^3 / 3 + x^5 / 5 - x^7 / 7 + ...
( 2 * b ) || ! ( 2 * b )

52

Re: OFF: Прошу подключиться к решению загадки… — II

Я не знаю, что конкретно имеется в виду под упрощением, но самый распространенный, и единственный что я знаю, это умножать на (-1)^n или (-1)^(n-1) в зависимости от знака первого слагаемого. Именно это было сделано в разложении арктангенса по Мэнчину вот тут

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

53 (изменено: Rumata, 2012-12-14 05:12:27)

Re: OFF: Прошу подключиться к решению загадки… — II

Возведение в степень - трудоемкая операция. Взятие степени от единицы (с минусом) - математически правильная запись, но очень затратная операция. Можно считать проще и быстрее. Например, представьте, что у нас нет операции возведения в степень. Кстати, на ассемблере это тоже нетривиальная задача, ведь решается она примерно так (в зависимости от языка)


pow(-1, n) == exp(n * log(-1)), в общем случае
pow(-1, n) == (-1) * (-1) * ... , n раз перемножить (-1) если n - целое
( 2 * b ) || ! ( 2 * b )

54 (изменено: kaster, 2012-12-14 05:56:18)

Re: OFF: Прошу подключиться к решению загадки… — II

Ну тогда так


mult = -1
tmp = 0
n = 0
while True:
    tmp += mult*f(n,x)
    n += 1
    mult *= -1
Rumata пишет:
pow(-1, n) == exp(n * log(-1)), в общем случае

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

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

55

Re: OFF: Прошу подключиться к решению загадки… — II

mult *= -1

еще проще

mult = -mult
kaster пишет:

Меня одолевают сомнения, т.к. логарифм определен только для положительных аргументов

Правильно одолевают. Но Math.pow(-1, 3) == -1, а Math.pow(-1, 2.9) или Math.pow(-1, 3.1) == -1,#IND. Поэтому и написал я именно так. Конечно же вместо -1 должно быть любое число, например x.

( 2 * b ) || ! ( 2 * b )

56

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata, не во всех языках можно взять логарифм отрицательного числа. Поэтому я не думаю, что

pow(-1, n) == exp(n * log(-1)), в общем случае

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

Другой вопрос – почему в языке где есть экспоненциальная функция, нет степенного?

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

57 (изменено: Rumata, 2012-12-14 08:43:12)

Re: OFF: Прошу подключиться к решению загадки… — II

почему в языке где есть экспоненциальная функция, нет степенного?

Я думаю из принципа минимализма. Натуральный логарифм есть - это базовая функция, через которую можно вычислить логарифм с любым другим основанием. Экспонента - это базовая функция, с ее помощью можно выразить любую степенную функцию. Опять же, это зависит от языка. В C/C++, Perl, Python это операция a**b, Basic - a^b, JS - метод, а Pascal - не умеет самостоятельно возводить в степень.

Честно говоря не хочется искать описание алгоритма возведения в степень в различных языках. Однако опыт подсказывает что алгоритм примерно таков:


func pow(a, b)
    if is_float(b)
        return exp(b * log(a))
    end if

    pow = 1
    for i = 1 to b
        pow *= a
    end for
end func

А возвращаемый результат зависит от реализации языка - то ли бросить исключение, то ли молча вернуть значение "НеЧисло".

( 2 * b ) || ! ( 2 * b )

58

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:

Pascal - не умеет самостоятельно возводить в степень

А логарифм с экспонентой есть. Действительно, чудо язык

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

59 (изменено: wisgest, 2016-08-23 22:32:59)

Re: OFF: Прошу подключиться к решению загадки… — II

OFF: возведение в степень в языках программирования

+ открыть спойлер
kaster пишет:
Rumata пишет:

Pascal - не умеет самостоятельно возводить в степень

А логарифм с экспонентой есть. Действительно, чудо язык

Не вижу чуда . Rumata правильно заметил, что возведение в нецелую степень всё-равно выполняется через  логарифм с экспонентой. Если надо, никто не мешает объявить в 1-2 строчки пользовательскую функцию.
И в не чудо-языках возведение в степень всё равно сделано в виде функции, т.е. чего-то внешнего по отношении к самому языку. Например, pow() в C.
А чудо-языки — это те, в которых логарифм с экспонентой — функции, а возведение в степень — операция самого языка (и нет перегрузки операторов).

Отсутствие встроенного возведения в целую степень в Pascal — тоже правильное решение, чтобы не развращать программистов, не то они начнут писать

s := 0;
for p := 0 to n do s := s + a[p]*x^p;

вместо

s := 0;
for p := n downto 0 do s := s*x + a[p];

или хотя бы

s := a[0]; pow := 1;
for p := 1 to n do begin pow := pow*x;  s := s + a[p]*pow end;

— сравните необходимое число умножений.

В тех же языках в которых имеется возведение в степень и при целом показателе оно осуществляется по отдельному алгоритму, скорее всего, используется алгоритм быстрого возведения в степень.
Его воплощение на JavaScript:

function /*double*/ intpow(/*double*/ x, /*int*/ n) {
    if (n < 0) return 1/intpow(x, -n);

    var pow = 1;
    while (n > 0) {
        if (n & 1) pow *= x;
        n >>= 1;
        x *= x;
    }
    return pow;
}

то же самое на Pascal:

function IntPow(x: Real; n: Integer): Real;
var Pow: Real;
begin
	if n < 0 then begin IntPow := 1/IntPow(x, -n); exit end;
	
	Pow := 1;
	while n > 0 do begin
		if Boolean(n and 1) then Pow := Pow * x;
		n := n shr 1;
		x := x * x
	end;
	IntPow := Pow
end;

60

Re: OFF: Прошу подключиться к решению загадки… — II

+ открыть спойлер
wisgest пишет:

Не вижу чуда

В моем разумении, e^x это такая же функция, как и a^x. Почему не сделать переменное основание, мне не понятно.

wisgest пишет:

Отсутствие встроенного возведения в целую степень в Pascal — тоже правильное решение

Ну, как непользователь Pascal'я, ничего определенного по этому поводу сказать не могу. Однако,

wisgest пишет:

чтобы не развращать программистов

в идеале, я полагаю, всех программистов надо так-же пересадить на ассемблер, по той же самой причине

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

61 (изменено: wisgest, 2012-12-16 06:06:39)

Re: OFF: Прошу подключиться к решению загадки… — II

OFF: возведение в степень в языках программирования

+ открыть спойлер
kaster пишет:

В моем разумении, e^x это такая же функция, как и a^x. Почему не сделать переменное основание, мне не понятно.

Не совсем: производная показательной функции пропорциональна ей самой, основание e — особое, т.к. в этом случае коэффициент пропорциональности равен 1.
Опять же, посмотри разложение a^x в степенной ряд и увидишь, что основание e — особое и всё-равно придётся переходить к нему через натуральный логарифм и предопределённая функция не будет иметь преимуществ перед делающей то же самое пользовательской.

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

kaster пишет:
wisgest пишет:

чтобы не развращать программистов

в идеале, я полагаю, всех программистов надо так-же пересадить на ассемблер, по той же самой причине

Да нет, но вот ведь наличие в Python «**» совратило тебя на бездумное (-1)**(n+1) вместо изящного sgn=-sgn и так будет во многих случаях.

62

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest пишет:

Не совсем: производная показательной функции пропорциональна ей самой, основание e — особое, т.к. в этом случае коэффициент пропорциональности равен 1.

Спасибо за ликбез, но я более чем знаком с математическими свойствами экспоненциальной функции, наряду со свойствами практически всех остальных элементарных и некоторых специальных функций. Речь шла про реализацию этой функции в том или ином ЯП. И мой вопрос касался, нельзя ли точно так же найти значения любой степенной функции.

wisgest пишет:

Да нет, но вот ведь наличие в Python «**» совратило тебя на бездумное (-1)**(n+1)

Что побудило тебя сделать вывод про бездумность? Сколько я потерял использовав внутреннюю функцию, без разного рода костылей для "повышения производительности"? Напомню, там где использовался знакопеременный ряд, количество итераций не превышало 20-ти.

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

63 (изменено: wisgest, 2012-12-17 14:53:55)

Re: OFF: Прошу подключиться к решению загадки… — II

kaster пишет:

Напомню, там где использовался знакопеременный ряд, количество итераций не превышало 20-ти.

Т.е., вероятно, около 60 дополнительных умножений.

kaster пишет:

Спасибо за ликбез

Всегда пожалуйста, но главное шло после процитированного тобой куска.

kaster пишет:

Речь шла про реализацию этой функции в том или ином ЯП. И мой вопрос касался, нельзя ли точно так же найти значения любой степенной функции.

Ну так я подозреваю что она ищется через ряд Маклорена:

wisgest пишет:

Опять же, посмотри разложение a^x в степенной ряд и увидишь, что основание e — особое и всё-равно придётся переходить к нему через натуральный логарифм и предопределённая функция не будет иметь преимуществ перед делающей то же самое пользовательской.

Я, мягко говоря, не очень хорошо знаком с системой команд арифметического сопроцессора (или сейчас это уже и не со-процессор, а команды для работы с числами с плавающей точкой включены в систему команд самого процессора?), но, по-моему, встроенного возведения в степень там нет, и, может быть, нет даже экспоненты…
----------------

wisgest пишет:

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

Кажется я сам могу предложить такой алгоритм одинаково (не)эффективный для любого основания. Попытаюсь его изложить.

Так как мы можем возводить в степень с целым показателем, для возведения в произвольную степень достаточно уметь возводить в степень с показателем большим 0, но меньшим 1.

Для этого перевернём шиворот-навыворот упомянутый выше алгоритм быстрого возведения в степень c натуральным показателем:
вместо прохода по двоичным разрядам целой части показателя от младших к старшим рассмотрим в противоположном порядке разряды дробной части
и вместо возведения в квадрат будем брать квадратный корень.
Для вычисления квадратного корня нет необходимости ни в общем действии возведения в степень, ни в экспоненте с натуральным логарифмом:
эта операция как раз, насколько я знаю, присутствует в системе команд арифметического сопроцессора, а если бы её и не было, то существуют различные алгоритмы его нахождения.

Не знаю, насколько эффективен такой алгоритм по сравнению с используемым для нахождения экспоненты, но если это так, то, возможно, он как раз используется на самом деле.

64

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest пишет:

Т.е., вероятно, около 60 дополнительных умножений.

А по времени? Для любой оптимизации нужны мотивы. Как правило это время. У каждого свои критерии, но я бы не стал (и я не стал) заморачиваться, если вместо 10 мс код будет считать 30 мс.

wisgest пишет:

Ну так я подозреваю что она ищется через ряд Маклорена:

Вот тут Numerical algorithms II: elementary functions пишут, что разлагают по Тейлору, с модификациями для ускорения сходимости. Но в целом, думаю, ты прав.

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

65

Re: OFF: Прошу подключиться к решению загадки… — II

Ещё задачка любителям арифметики.
Составить формулу, по которой можно узнать время, когда минутная стрелка часов опережает часовую на n градусов.

66

Re: OFF: Прошу подключиться к решению загадки… — II

Невозможно, если заранее не известно положение часовой стрелки.

Разработка AHK-скриптов:
e-mail dfiveg@mail.ru
Telegram jollycoder

67

Re: OFF: Прошу подключиться к решению загадки… — II

Положение часовой стрелки задаёт пользователь от 0 до 11 часов.

68 (изменено: wisgest, 2012-12-28 21:20:41)

Re: OFF: Прошу подключиться к решению загадки… — II

Для заданного угла n (0<=n<=360) и каждого целого количества часов H=0..11
вычисляем количество минут по формалам:
M=(n*2+H*60)/11
и
M=(n*2+H*60-720)/11
Если получено 0<=M<60, то H:M — ответ.

n = 0+InputBox("n=")
If n<0 Or n>360 Then WScript.Quit 1
Result=""
For H=O To 11
  M=(n*2+H*60)/11
  If M<60 Then           Result = Result & vbNewLine & H & " : " & M
  M=(n*2+H*60-720)/11
  If M>=0 And M<60 Then  Result = Result & vbNewLine & H & " : " & M
Next
MsgBox Result

Вроде бы формулы для подсчёта количества минут  взаимоисключающие и до определённого H рассчёт идёт исключительно по первой формуле, затем — исключительно по второй; так что решение можно уточнить.

69 (изменено: kaster, 2012-12-29 03:41:28)

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu
То есть, это такие странные дискретные часы, часовая стрелка у которых движется только по целым часам? Перескакивая, к примеру, от 2 сразу 3 без прохождения промежуточных положений?

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

70 (изменено: Rumata, 2012-12-29 05:02:38)

Re: OFF: Прошу подключиться к решению загадки… — II

Условия задачи несколько некорректны.

1. Угловые расстояния (если можно так сказать) непрерывны. Положение стрелок часов строго дискретно, Нельзя произвольно указать относительное положение стрелок в произвольных градусах - их относительное положение также дискретно.

Полный круг составляет 360 градусов. На циферблате две шкалы. Одна - минутная ("малая"), 60 делений. Расстояние между двумя соседними делениями - 6 градусов. Другая - часовая ("большая"), 12 делений. Расстояние между делениями 30 градусов.

Между полными часами (ЧЧ:00) часовая стрелка занимает определенные, дискретные положения на "малой шкале". Их всего четыре, которые меняются каждые 12 минут: ЧЧ:12, ЧЧ:24, ЧЧ:36, ЧЧ:48. Пока минутная стрелка оббегает, например, время от 12 до 23, часовая стоит на одном месте и перескакивает на следующее деление на 24 минуте, и т.д.

2. Неочевидна фраза "минутная стрелка часов опережает часовую на n градусов". С какого момента минутная стрелка опережает часовую, а когда она отстает? Чем является - "опережением" или "отставанием" - положение, когда стрелки совпадают, или диаметрально противоположно?

Примем за начало всех угловых отсчетов положение любой стрелки в 0 и рассмотрим следующий пример.

Показания часов 00:36. Часовая стрелка находится между 0 и 1 "большой шкалы" и показывает на 3 деление "малой шкалы" - это соответствует 18 градусам. Минутная стрелка находится на первом делении "малой шкалы" после цифры 7 "большой шкалы", или 216 градусов (36 * 6). Разница составляет 198 градусов (216 - 18).

Предыдущее положение часовой стрелки второе деление "малой шкалы", оно соответствует показаниям минут между 24 и 35, включительно. Время, соответствующее диаметрально противоположному положению стрелок, наступит в 00:32 - часовая стрелка на втором делении после 0, минутная на втором после 6. Это соответствует расстоянию между стрелками в 180 градусов. В этот момент минутная опережает часовую или уже догоняет?

( 2 * b ) || ! ( 2 * b )

71 (изменено: wisgest, 2012-12-29 10:25:24)

Re: OFF: Прошу подключиться к решению загадки… — II

kaster пишет:

То есть, это такие странные дискретные часы, часовая стрелка у которых движется только по целым часам? Перескакивая, к примеру, от 2 сразу 3 без прохождения промежуточных положений?

Думаю, ypppu имел в виду именно часы с равномерно вращающимися стрелками. Я исходил из этого. Например, в 5:30 часовая стрелка находится точно между 5 и 6 часами, а минутная указывает на 6 часов, т.е. опережает часовую на n=15 градусов.

Rumata пишет:

С какого момента минутная стрелка опережает часовую, а когда она отстает?

Всегда опережает и всегда отстаёт. Например, если отстаёт на 1 градус, то опережает на 359.

72

Re: OFF: Прошу подключиться к решению загадки… — II

Углы между стрелками действительно дискретны. Дискретность определяется(насколько я понимаю) храповиком маятника, т.е. частотой колебания этого маятника. Это выражается в числе шагов секундной стрелки. Минутная и часовая "соеденены" с секундной "непрерывной" передачей(редуктор). В дешёвых часах шаг 1 секунда(что для минутной это составляет 360/60/60 = 0.1 градус, для часовой 360/12/60/60 ~ 0.0083 градуса), в часах получше секундная стрелка может совершить 3-4 перемещения за одну секунду, соответственно шаг перемещения минутной стрелки упадёт до 0.025, а часовой до 0.002.

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

Условие "минутная стрелка часов опережает часовую на n градусов" полагаю нужно трактовать так: угол между часовой стрелкой и минутной отсчитывается по ходу часов, и лежит в пределе [0;360).

73 (изменено: Rumata, 2012-12-29 10:15:38)

Re: OFF: Прошу подключиться к решению загадки… — II

Всегда опережает и всегда отстаёт. Например, если отстаёт на 1 градус, то опережает на 359.

Звучит витиевато, но идея ясна. Есть другое мнение. Например, угол между стрелками < 180, значит минутная опережает. Обратное утверждение >= 180 - догоняет.

Но я бы уточнил Ваш пример с учетом дискретности - отстает на 6 градусов, или опережает на 354.

( 2 * b ) || ! ( 2 * b )

74

Re: OFF: Прошу подключиться к решению загадки… — II

kaster пишет:

ypppu
То есть, это такие странные дискретные часы, часовая стрелка у которых движется только по целым часам? Перескакивая, к примеру, от 2 сразу 3 без прохождения промежуточных положений?

В жизни мгновенно ничего не происходит. Я имел в виду именно обычные часы, где стрелки поворачиваются плавно. В этом смысле wisgest меня правильно понял.
Ещё я зря сказал "формула". Пожалуй, лучше было "алгоритм" или "скрипт". Ведь за 12 часов всего 11 раз случается, что минутная стрелка опережает часовую. То есть можно составить скрипт, в котором не требуется вводить время в часах, а только угол. А на выходе получаем 11 возможных результатов.
И ещё я специально не использую понятие "отстаёт", чтобы не было лишней путаницы.

75 (изменено: Rumata, 2012-12-29 10:29:51)

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu, коллега, а что Вы вкладываете в выражение "минутная стрелка опережает часовую"?

обычные часы, где стрелки поворачиваются плавно

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

( 2 * b ) || ! ( 2 * b )

76

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Пожалуй, лучше было "алгоритм" или "скрипт".

Ну, в черне алгоритм прост .
Берём 0(12) часов за начало отсчёта.
m - минуты, h - часы.
Положение часовой стрелки(альфа) = 30*h + 0.5*m
Положение минутной стрелки(бета) = 6*m
Задаваемый пользователем угол(гама) = |альфа - бета|

Дальше получаем функцию для m(с учётом того угол положения какой стрелки больше, как минимум две). Правда решил не полностью, поэтому публиковаться пока не готов(кажется я где-то что-то не учёл).

77

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:

ypppu, коллега, а что Вы вкладываете в выражение "минутная стрелка опережает часовую"?

обычные часы, где стрелки поворачиваются плавно

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

Rumata, где-то я уже это видел. Вместо решения задачки участник начинает докапываться до мелочей. Следующим шагом выяснится, что атомы металла стрелок движутся хаотично, а время искажается гравитацией.

78

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu, с заданными условиями задача решается, но не надо забывать об очевидном. А так получается, что у в задаче одни часы, а я думаю о других часах.

( 2 * b ) || ! ( 2 * b )

79

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:

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

Прыжки различимы только для секундной стрелки, или при очень длинной минутной стрелке(например, уличные часы), или при рассматривании минутной(тем более часовой) стрелки с увеличением. На наручных часах движение минутной и часовой стрелки вполне можно принимать плавным.
Так как шаг часовой стрелки периодическая дробь, в реальных условиях число вариантов исходных данных при которых будет возможен точный ответ будет ограничен. Но так как задача для "любителей арифметики", а арифметика это начальная школа - не стоит усложнять условия через чур. Хотя указать на предпосылки принятые для реализации конкретного решения конечно нужно .

80 (изменено: Rumata, 2012-12-29 10:54:29)

Re: OFF: Прошу подключиться к решению загадки… — II

BeS Yara, эта оговорка хорошая (но все-таки не соответствует действительности - помню как в детстве любил наблюдать за движением стрелок - и они прыгали; Вы и сами упомянули о маятнике часового механизма). Хотелось, чтобы этот момент был оговорен в условиях задачи.

( 2 * b ) || ! ( 2 * b )

81

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata, тут логика простая. Если в условиях не указано, как именно перемещаются стрелки, значит они поворачиваются с постоянной угловой скоростью относительно центра циферблата, по часовой стрелке (если смотреть с лицевой стороны циферблата ). Если б они поворачивались мгновенно, об этом было бы сказано.

82

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:

помню как в детстве любил наблюдать за движением стрелок - и они прыгали

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

Rumata пишет:

Но я бы уточнил Ваш пример с учетом дискретности - отстает на 6 градусов, или опережает на 354.

Почему же? Опережает на 359° ровно в 7:38.

Похоже, для каждого целого n, существует ровно один ответ с целым числом минут.

83 (изменено: Rumata, 2012-12-29 11:34:26)

Re: OFF: Прошу подключиться к решению загадки… — II

ypppu пишет:

Следующим шагом выяснится, что атомы металла стрелок движутся хаотично, а время искажается гравитацией.

ypppu пишет:

если смотреть с лицевой стороны циферблата

А не надо язвить. Вот пример коллеги BeS Yara, почти повторяет мое решение (за исключением взятия модуля числа), это решение выглядит верным, но последовательность действий неверна и результат не верно отражает действительность. Вы же сами говорите о постоянном последовательном вращении стрелок



var angle = 30;

for (var h = 0; h < 12; h++) {
    var hAngle = h * 30;
    for (var m = 0; m < 60; m++) {
        var mAngle = m * 6;
        var diff = mAngle - hAngle;
        if ( diff == angle ) {
            WScript.Echo('hh:mm = ', h, m);
        }
    }
}
( 2 * b ) || ! ( 2 * b )

84

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest пишет:

Похоже, для каждого целого n, существует ровно один ответ с целым числом минут.

Опережение на 1° достигается за каждые 4 часа 22 минуты. Вот начало этой последовательности для целых n, начиная с 0:
0:00, 4:22, 8:44, 1:06, 5:28, 9:50, 2:12…

85

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata пишет:

(за исключением взятия модуля числа)

Да, с модулем я погорячился - с ним получается немного не тот угол при "отставании" минутной стрелки.

Исходя из того что "угол опережения" это угол от часовой до минутной стрелки, отложенный "по часовой стрелке":
альфа(положение часовой стрелки)
бета(положение минутной стрелки)
гама(угол "опережения")
h - час
m - минуты
Для случая когда минутная стрелка "впереди" часовой(например 15 минут второго):
m = (гама + K1*h)/(K2 - K3)
Для случая когда минутная стрелка "позади" часовой(например 5 минут третьего):
m = (360 - K1*h - гама)/(K3 - K2)

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

Option Explicit
Dim h 'час
h = 1 'задаёт "пользователь"
h = h - 12*(h\12)

Dim gama 'угол опережения часовой стрелки минутной
gama = 312 'задаёт "пользователь"
gama = Abs(gama) - 360*(gama\Abs(360)) '"пользователь" может попасться хитрый

Dim K1, K2, K3
K1 = 360/12 '30 градусов в часе(для часовой стрелки)
K2 = 360/60 '6 градусов в минуте(для минутной стрелки)
K3 = 360/12/60 '0.5 градусов в минуте(для минутной стрелки)

Dim m1, m2, mm1, mm2 'минут
m1 =  (gama + K1*h)/(K2 - K3) 'без учёта периода в 60 минут
mm1 = (m1 - 60*(m1\60)) 'с учётом периода 60 минут

m2 =  (360 - K1*h - gama)/(K3 - K2) 'без учёта периода в 60 минут
mm2 = (m2 - 60*(m2\60)) 'с учётом периода 60 минут

If K2*m1 > K1*h + K3*m1 Then
    wscript.echo "1: время(точно): " & h & " часов " & mm1 & " минут"
    wscript.echo "1: время(округлённо): " & h & " часов " & Int(mm1) & " минут"
  Else
    wscript.echo "2: время(точно): " & h & " часов " & mm2 & " минут"
    wscript.echo "2: время(округлённо): " & h & " часов " & Int(mm2) & " минут"
End If

86 (изменено: ypppu, 2012-12-29 12:00:45)

Re: OFF: Прошу подключиться к решению загадки… — II

Rumata, и как Вы будете решать задачу, если я скажу, что стрелка движется рывками? Будете требовать предоставить величину скорости и ускорения?

Нельзя просто так задать задачу, чтобы:
а) никто не придирался к условиям
б) никто не обижался

87

Re: OFF: Прошу подключиться к решению загадки… — II

как Вы будете решать задачу, если я ...

А это уж Вы придираетесь

( 2 * b ) || ! ( 2 * b )

88

Re: OFF: Прошу подключиться к решению загадки… — II

По поводу нахождения числа П: в качестве варианта можно воспользоваться рядом Лейбница, который представляет из себя разложение прямой y=x в ряд Фурье при аргументе П/2 и позволяет получить число П.

VBScript:


 s = 0
 k = 1

 For i = 1 to 200000

     s = s + 4 * k/(2 * (i - 1) + 1)

     'Переключатель знака
     If k = 1 Then 
        k = - 1
     Else
        k = 1
     End If
 Next

 MsgBox Round(s,5), vbSystemModal

89 (изменено: Aскет, 2013-01-13 20:07:21)

Re: OFF: Прошу подключиться к решению загадки… — II

Можно ли из 6 спичек построить 4 равносторонних треугольника?

90 (изменено: YMP, 2013-01-13 20:09:26)

Re: OFF: Прошу подключиться к решению загадки… — II

Тетраэдр (греч. ?????????? — четырёхгранник) — простейший многогранник, гранями которого являются четыре треугольника. У тетраэдра 4 грани, 4 вершины и 6 рёбер.

91 (изменено: Aскет, 2013-01-14 03:44:18)

Re: OFF: Прошу подключиться к решению загадки… — II

А если в плоскости?

92

Re: OFF: Прошу подключиться к решению загадки… — II

Так примерно:
http://i.imgur.com/1AdIB.jpg

Разработка AHK-скриптов:
e-mail dfiveg@mail.ru
Telegram jollycoder

93

Re: OFF: Прошу подключиться к решению загадки… — II

Ну, если примерно, то да. Здесь пять треугльников вместе с большим. А четыре можно получить по разному.

94

Re: OFF: Прошу подключиться к решению загадки… — II

А четыре можно получить по разному.

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

95

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest, Malcev, я вот смотрю на эту картинку и вижу четрыре равносторонних треугольника на плоскости, образованных шестью равными отрезками.
Upd: вернее 5 треугольников, заметил.
http://i.imgur.com/1AdIB.jpg

96

Re: OFF: Прошу подключиться к решению загадки… — II

Ну ещё так:
http://i.imgur.com/gJBpP.jpg

Разработка AHK-скриптов:
e-mail dfiveg@mail.ru
Telegram jollycoder

97 (изменено: Aскет, 2013-01-14 15:45:33)

Re: OFF: Прошу подключиться к решению загадки… — II

На самом деле нужно взять 3 обычные спички, сложить их как "Y" (с углом развала в 120 градусов) и взять 3 длинных спички типа "Для камина", соединив ими концы спичек, образующих "Y".
Получим 3 равносторонних треугольника (без "отрубей"), вписанных 4-й равносторонний.

Но можно обойтись и 6-ю простыми, сложив методом "наложения друг на друга", как в http://i.imgur.com/1AdIB.jpg (рисунок напомнил что-то масонское, "всевидящее око" какое-то )

98

Re: OFF: Прошу подключиться к решению загадки… — II

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

autoit@conference.jabber.ru - Конференция скриптового языка AutoIt на jabber.ru

99

Re: OFF: Прошу подключиться к решению загадки… — II

wisgest, Malcev, я вот смотрю на эту картинку и вижу четрыре равносторонних треугольника на плоскости, образованных шестью равными отрезками.

А на самом деле их 5

Ну ещё так:

Пол-часа крутил спички, а до твоего ответа так и не додумался.
Наверное, это единственный способ составить 4 одинаковых равносторонних треугольника в одной плоскости.

100

Re: OFF: Прошу подключиться к решению загадки… — II

http://math.all-tests.ru/sites/math.all-tests.ru/files/images/468-problem.png
Переложите 1 спичку таким образом, чтобы равенство стало верным.