Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Сб июл 21, 2018 13:53

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
Читая статью Дейкстры, увидел у него задачку, которую сформулирую так:
для целых чисел от 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
....

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт май 31, 2012 00:29 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
2 1 1
4 2 2

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт май 31, 2012 10:05 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
вопрос писал(а):
Тут все в порядке?

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

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

Насчет про пробелы в строке, не знаю.
Вот минут за пять решил эту задачку(чего там Дейкстра мучился). :)
Код:
: 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. Думаю, что на обычном форте это будет подольше.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт май 31, 2012 10:46 
Не в сети
Аватара пользователя

Зарегистрирован: Пт апр 13, 2012 11:57
Сообщения: 142
Благодарил (а): 3 раз.
Поблагодарили: 0 раз.
вопрос писал(а):
Цитата:
2 1 1
4 2 2

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

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

_________________
Дейкстраординарный


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт май 31, 2012 10:53 
Не в сети
Аватара пользователя

Зарегистрирован: Пт апр 13, 2012 11:57
Сообщения: 142
Благодарил (а): 3 раз.
Поблагодарили: 0 раз.
Чёрт, я, судя по всему, не верно понял условия. От 1 до n, а я же решал, как если бы нужно было ввести конкретное число, и программа раскладывала его на множители по заданному выражению. :o

_________________
Дейкстраординарный


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт май 31, 2012 15:21 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
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. Изыски Дейкстры с лихвой компенсируются использованием сопроцессора, что я и сделал.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт май 31, 2012 16:14 
Не в сети
Аватара пользователя

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

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

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт июн 14, 2012 00:28 
Не в сети
Аватара пользователя

Зарегистрирован: Пт апр 13, 2012 11:57
Сообщения: 142
Благодарил (а): 3 раз.
Поблагодарили: 0 раз.
chess писал(а):
У Дейкстры было так как вы подумали.
У меня чуть сложнее условие, чтоб интерес какой-то был.

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

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

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

_________________
Дейкстраординарный


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт июн 14, 2012 12:31 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
Zinger писал(а):
Знаю, кстати, первым, кто сообщил мне о том, что мы, я и Дейкстра, родственные души с крайне близким образом мысли, был не кто иной, как старина gudleifr, он же, между прочим, отметил, что задачи наподобие этой ни в коем случае не решаются на предложенный вами манер.

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

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задачка из статьи Дейкстры
СообщениеДобавлено: Чт июн 14, 2012 18:24 
Не в сети
Аватара пользователя

Зарегистрирован: Пт апр 13, 2012 11:57
Сообщения: 142
Благодарил (а): 3 раз.
Поблагодарили: 0 раз.
chess писал(а):
Zinger писал(а):
Знаю, кстати, первым, кто сообщил мне о том, что мы, я и Дейкстра, родственные души с крайне близким образом мысли, был не кто иной, как старина gudleifr, он же, между прочим, отметил, что задачи наподобие этой ни в коем случае не решаются на предложенный вами манер.

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

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

_________________
Дейкстраординарный


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB