Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 12:50

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: это не решение задачи
СообщениеДобавлено: Чт июн 14, 2012 19:45 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу :ищем её, длина пути поиска и будет объём памяти

Теперь остается самая малость, написать программу с использованием
заданного в условии функционала. :)

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *Помогите найти объем памяти
СообщениеДобавлено: Чт июн 14, 2012 19:49 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
вопрос писал(а):
если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу

а если размер бит?
а до гига диапазон лишь в тесте, может там 16 Гбит, или 256? а может 3 бита 8) А нужно точно знать, сколько 8)

chess писал(а):
Теперь остается самая малость, написать программу с использованием заданного в условии функционала.

вот вот
ибо я чем дальше тем злее, могу начать зверствовать...

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *Помогите найти объем памяти
СообщениеДобавлено: Чт июн 14, 2012 19:58 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
WingLion писал(а):
Читаем все остальное до предполагаемого предела - 1Гбита, проверяя, что все остальные данные повторяются. Если появляются неповторяющиеся данные - увеличивать N на единицу и снова на п.3.

Тут, возможно, есть та трудность, что данные с самого начала могут быть повторяющимися и именно так, чтобы дезориентировать решающего
Цитата:
а если размер бит?
ну мы обнулим его 2**30 раз, а после этого начав поиск по кругу, найдём на первом же шагу, определив объём памяти в 1 бит


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *Помогите найти объем памяти
СообщениеДобавлено: Чт июн 14, 2012 20:02 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
mOleg писал(а):
скажем, размер памяти - простое число


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


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

Тогда второй вариант с записью последовательных чисел, начиная с нуля, пока первый ноль не затрется.
Однобитный вариант обнаружится сразу, потому что на уже на втором бите единичка затрет первый нолик.
Собственно, сохранять содержимое в условии не сказано, поэтому просто пишем нули, проверяя, что запись единичкс, записанная в адрес 2^N с целыми N не попадает в нулевой адрес...

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

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


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

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
mOleg писал(а):
: текущий ( --> addr ) адрес объем MOD память + ;
: влево ( --> ) адрес 1 - TO адрес ;
: вправо ( --> ) адрес 1 + TO адрес ;
: прочесть ( --> flag ) текущий B@ 0<> ;
: изменить ( --> ) текущий B@ -1 XOR текущий B! ;[/pre]
вместо xxx подставить случайные числа, массив проинициализировать случайным содержимым. Размер любой в диапазоне от одной ячейки до 1 Гигабита. Обратите внимание на то, что адресация закольцована, т.е. перейдя последний бит попадаем в первый, и наоборот.

Если можно использовать слово текущий, то задача решается тривиально.
Иначе:
Методом вопроса задача решается за линейное время, но должно быть ограничение на макс. объём.
Без ограничения решается за квадратичное: пишем 1, затем пишем i нулей (i=1..бесконечность), возвращаемся на i бит и проверяем, жива ли 1.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *Помогите найти объем памяти
СообщениеДобавлено: Пт июн 15, 2012 09:30 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Код:
: сколькобит ( --> # )
  0x80000000 0 DO прочесть IF изменить THEN  вправо LOOP
  прочесть 0= IF изменить THEN
  0x80000000 0 DO прочесть IF I 1+ LEAVE THEN вправо LOOP  ;

Ps. Вариант с неизвестным пределом объема памяти не рассматриваю, так как
он не имеет смысла с чисто вычислительной стороны.
Решать вариант с известным пределом объема памяти с возвратом(2 алгоритм от dinamic-wind)
тоже особого смысла нет, так как даже при малом объеме памяти он проигрывает по времени счета приведенному решению.
Да, забыл. Решение на манипуляторах будет выглядеть так:
Код:
: сколькобит ( --> # )
0x80000000 0 ['] прочесть ['] изменить ['] вправо
5\01D2Xi3Xt4XL2XZi3Xt01D2XiI`1+Qt4XL ;

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: это не решение задачи
СообщениеДобавлено: Вт июн 19, 2012 15:40 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Код:
\ симулятор

REQUIRE CHOOSE lib\ext\rnd.f

0 VALUE addr
0 VALUE abeg
0 VALUE aend
0 VALUE vol

: create-memory ( n -- )
CHOOSE 1+ DUP TO vol ALLOCATE THROW TO abeg
abeg vol + TO aend
abeg vol CHOOSE + TO addr
vol . abeg . aend . addr . ;

: read ( -- f ) addr C@ ;
: change        addr C@ INVERT addr C! ;
: left          addr abeg = IF aend ELSE addr 1- THEN TO addr ;
: right         addr aend = IF abeg ELSE addr 1+ THEN TO addr ;

\ реализация алгоритма определения объема памяти ( сложность O(Nlog2N))
: volume ( -- # ) 0 m! 1 M! 0 MM! 0 f!
w1( read 0= IF change THEN )
w0( read IF change THEN )
nw0( M 0 ?DO right w0 LOOP )
nl( M 0 ?DO left LOOP )
r0?( read 0= )
BEGIN w1 nw0 nl r0?
      IF M m - 1 =
         IF CR M 1- . EXIT ELSE M is MM M m + 2/ is M 1 is f THEN
      ELSE M is m f 0= IF M 2* is M ELSE MM is M 0 is f THEN THEN
AGAIN ;

STARTLOG
12345678 create-memory volume
log
Код:
9053092 17170468 26223560 24377646  \ объем  нач. адрес  кон. адрес  текущий адрес
9053092 \ результат
Ok

ps. Реализация быстрого алгоритма, для объема до 1000000 ячеек быстрее чем мое ранее приведенное решение.
1. Можно еще чуть ускорить(процентов на 30) исключив операцию записи нулей в заведомо обнуленные ячейки.
Это можно сделать оформив процедуру nw0 по другому, а именно, nw0( m 0 ?DO right LOOP M m ?DO right w0 LOOP )
2. Привожу здесь, так как решение не на plain Forth.
3. Задачу можно усложнить поставив в условии требование о сохранении исходного содержимого памяти.

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


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

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


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

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


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

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