Forth
http://fforum.winglion.ru/

Задачка из статьи Дейкстры
http://fforum.winglion.ru/viewtopic.php?f=19&t=2852
Страница 1 из 1

Автор:  chess [ Ср май 30, 2012 16:31 ]
Заголовок сообщения:  Задачка из статьи Дейкстры

Читая статью Дейкстры, увидел у него задачку, которую сформулирую так:
для целых чисел от 1 до n вывести все пары x y для каждого n, такие, что n=x*x+y*y, при этом дб x>=y>=0
Код:
: nxy. ( n -- )
( здесь ваш текст решения )
;
формат вывода результатов такой:
Код:
 
2   1 1
4   2 2
5   2 1
8   2 2
10   3 1
13   3 2
........
45   6 3
50   5 5  7 1
....

Автор:  вопрос [ Чт май 31, 2012 00:29 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

Цитата:
2 1 1
4 2 2

Тут все в порядке?

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

Автор:  chess [ Чт май 31, 2012 10:05 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

вопрос писал(а):
Тут все в порядке?

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

Нет конечно, и согласно условию это еще не все, но формат вывода(не результаты вывода) - дб таким каким приведен в посте.

Насчет про пробелы в строке, не знаю.
Вот минут за пять решил эту задачку(чего там Дейкстра мучился). :)
Код:
: nxy. ( n -- x0 y0 ... xn yn )
s( $ -4 @P=A $ -4 0=@P 0SQRT $ -4 @P=0- $ -4 A=@P ) \ n -- sqrt(n)  корень
1\Y'2!0`1+`0GI[s]`1+I`2/[s]GJId*-[s]d'1!d*Id*+J=I1<~&1`0<~&i2J=~iJ'2!\J.`2StI.1.`1StLL ;

: tst 100 nxy. ; STARTLOG tst
лог.
Код:
0   0 0
1   1 0
2   1 1
4   2 0
5   2 1
8   2 2
9   3 0
10   3 1
13   3 2
16   4 0
17   4 1
18   3 3
20   4 2
25   4 3  5 0
26   5 1
29   5 2
32   4 4
34   5 3
36   6 0
37   6 1
40   6 2
41   5 4
45   6 3
49   7 0
50   5 5  7 1
52   6 4
53   7 2
58   7 3
61   6 5
64   8 0
65   7 4  8 1
68   8 2
72   6 6
73   8 3
74   7 5
80   8 4
81   9 0
82   9 1
85   7 6  9 2
89   8 5
90   9 3
97   9 4
98   7 7
100   8 6  10 0
Ok

ps. Думаю, что на обычном форте это будет подольше.

Автор:  Zinger [ Чт май 31, 2012 10:46 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

вопрос писал(а):
Цитата:
2 1 1
4 2 2

Тут все в порядке?

вопрос, нет, разумеется, тут не всё в порядке, более того, вы оказались несколько внимательнее меня. Взявшись за решение задачи и сделав произвольную выборку чисел дабы вывести систему, я обнаружил брешь лишь на 44, которое, по-моему, также невозможно представить в соответствии с данными условиями. Следовательно, полагаю, должны быть случаи, предусматривающие легитимную ." инвалидность".
Единственный, кто в силах сформулировать корректное условие приняв во внимание всевозможные "подводные камни", так это VoidVolker. Стажировавшись в MITе ещё будучи студентом МФТИ, закончив университет он длительное время проработал в Беркли, далее поступил на службу в АНБ, заняв место главного специалиста по криптографии. Сейчас он возглавляет один из самых перспективных и многообещающих проектов NASA. Думаю, никому и в голову не придёт, что у профессионала такого уровня могут возникнуть загвоздки со столь плёвой проблемой. :cry: (ой, какой здесь тоскливый край, должен ведь быть зелёным и "в голос")

Автор:  Zinger [ Чт май 31, 2012 10:53 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

Чёрт, я, судя по всему, не верно понял условия. От 1 до n, а я же решал, как если бы нужно было ввести конкретное число, и программа раскладывала его на множители по заданному выражению. :o

Автор:  chess [ Чт май 31, 2012 15:21 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

Zinger писал(а):
Чёрт, я, судя по всему, не верно понял условия. От 1 до n, а я же решал, как если бы нужно было ввести конкретное число, и программа раскладывала его на множители по заданному выражению.

У Дейкстры было так как вы подумали.
У меня чуть сложнее условие, чтоб интерес какой-то был.
Для его условия решение слишком примитивно:
Код:
: xy. ( n -- x0 y0 ... xn yn )
s( $ -4 @P=A $ -4 0=@P 0SQRT $ -4 @P=0- $ -4 A=@P )
1\0[s]`1+0`2/[s]G0Id*-d[s]d'1!d*=iI.1.tL ;

Код:
174250 xy.
305 285 345 235 359 213 395 135 397 129 411 73 415 45 417 19
Ok

ps. Изыски Дейкстры с лихвой компенсируются использованием сопроцессора, что я и сделал.

Автор:  VoidVolker [ Чт май 31, 2012 16:14 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

Zinger писал(а):
Взявшись за решение задачи и сделав произвольную выборку чисел дабы вывести систему, я обнаружил брешь лишь на 44, которое, по-моему, также невозможно представить в соответствии с данными условиями. Следовательно, полагаю, должны быть случаи, предусматривающие легитимную ." инвалидность".
Единственный, кто в силах сформулировать корректное условие приняв во внимание всевозможные "подводные камни", так это VoidVolker. Стажировавшись в MITе ещё будучи студентом МФТИ, закончив университет он длительное время проработал в Беркли, далее поступил на службу в АНБ, заняв место главного специалиста по криптографии. Сейчас он возглавляет один из самых перспективных и многообещающих проектов NASA. Думаю, никому и в голову не придёт, что у профессионала такого уровня могут возникнуть загвоздки со столь плёвой проблемой. :cry: (ой, какой здесь тоскливый край, должен ведь быть зелёным и "в голос")

И когда это я успел? :shock: Так, к слову, к США отношусь совсем не положительно и не стал бы на них ни за какие коврижки. Да и на какую-либо другую страну тоже.

Автор:  Zinger [ Чт июн 14, 2012 00:28 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

chess писал(а):
У Дейкстры было так как вы подумали.
У меня чуть сложнее условие, чтоб интерес какой-то был.

Знаю, кстати, первым, кто сообщил мне о том, что мы, я и Дейкстра, родственные души с крайне близким образом мысли, был не кто иной, как старина gudleifr, он же, между прочим, отметил, что задачи наподобие этой ни в коем случае не решаются на предложенный вами манер.

VoidVolker писал(а):
И когда это я успел? :shock: Так, к слову, к США отношусь совсем не положительно и не стал бы на них ни за какие коврижки. Да и на какую-либо другую страну тоже.

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

Автор:  chess [ Чт июн 14, 2012 12:31 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

Zinger писал(а):
Знаю, кстати, первым, кто сообщил мне о том, что мы, я и Дейкстра, родственные души с крайне близким образом мысли, был не кто иной, как старина gudleifr, он же, между прочим, отметил, что задачи наподобие этой ни в коем случае не решаются на предложенный вами манер.

Конкурс решения задач он для решения задач. Ссылка на имя Дейкстры была только для того чтобы как-то назвать задачу.
Условие задачи изложено однозначно и полно (информации дополнительной из материалов от Дейкстры не требовалось).
Решение задачи должно давать результат в соответствии с поставленным условием, при этом способ решения не имеет значения,
если это особо не оговорено в условии.

Автор:  Zinger [ Чт июн 14, 2012 18:24 ]
Заголовок сообщения:  Re: Задачка из статьи Дейкстры

chess писал(а):
Zinger писал(а):
Знаю, кстати, первым, кто сообщил мне о том, что мы, я и Дейкстра, родственные души с крайне близким образом мысли, был не кто иной, как старина gudleifr, он же, между прочим, отметил, что задачи наподобие этой ни в коем случае не решаются на предложенный вами манер.

Конкурс решения задач он для решения задач. Ссылка на имя Дейкстры была только для того чтобы как-то назвать задачу.
Условие задачи изложено однозначно и полно (информации дополнительной из материалов от Дейкстры не требовалось).
Решение задачи должно давать результат в соответствии с поставленным условием, при этом способ решения не имеет значения,
если это особо не оговорено в условии.

Действительно, конкурс решения задач предполагает решение задач, равно как и туалетная бумага создана для туалетных нужд. Однако, вы упускаете из виду один первостепенный момент, а именно, смысл конкурса как конкурса заключается в том, чтобы выявить наиболее оригинальные, элегантные, изящные, если короче, то простые и красивые решения, причём, совершенно не важно, какого рода сама задача - программистская, математическая, или шахматная. Я легко допускаю, что вам глубоко безразлична степень искуса, с которым решена задача, что же, в таком случае, вы всего-навсего тяготеете к топорным решениям и в этом нет ничего предосудительного, как говорится, бог вам судья; но позвольте и нам, мне и Дейкстре, людям с врождённым и несводимым чувством прекрасного иметь свою точку зрения, от вас большего не требуется. В конце концов, повторюсь, вас никто не осуждает, речь идёт только о том, что если бы в жюри конкурса сидели мы с gudleifr'ом, то ваше решение отправилось бы прямиком в утиль, но это ведь не повод накладывать на себя руки, правда?
Теперь насчёт упоминания Дейкстры в контексте вашей задачи, как ни странно, но вы правы, оно (упоминание) не обязательно. Другое дело, что это необходимо исходя из норм банального этикета, так как ваша задача очевидная вариация на проблему, предложенную Дейкстрой, и, хочу заметить, его постановка смотрится куда интереснее, не даром же я угадал, как должна выглядеть ваша задача в аутентичном варианте, ибо мы, я и Дейкстра, как один. Впрочем, продолжая об этикете, вынужден признать, что нынешним поколением Интернет-пользователей он зачастую абсолютно игнорируется, но так было далеко не всегда. Изначально Интернет служил дискуссионной площадкой сугубо для специалистов высокого класса и, смею вас заверить, уровень обмена мнениями был соответствующим, теперь же, когда по первому зову всякого школьника или домохозяйки приходит какой-нибудь студентик с пушком под носом и закусывает, а после втыкает витую пару в компьютер, ситуация резко изменилось. И всё же надеюсь, что форум Винглиона, как последний оплот истой культуры на просторах современного Интернета, не уподобится прочим, превратившимся в массовые плевательницы, ресурсам. Так не допустим же обнищания нравов общими усилиями!

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/