Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 10:38

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - это не решение задачи
Автор Сообщение
  Заголовок сообщения:  Re: это не решение задачи  Ответить с цитатой
Код:
\ симулятор

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. Задачу можно усложнить поставив в условии требование о сохранении исходного содержимого памяти.
Сообщение Добавлено: Вт июн 19, 2012 15:40
  Заголовок сообщения:  Re: *Помогите найти объем памяти  Ответить с цитатой
Код:
: сколькобит ( --> # )
  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 ;
Сообщение Добавлено: Пт июн 15, 2012 09:30
  Заголовок сообщения:  Re: *Помогите найти объем памяти  Ответить с цитатой
mOleg писал(а):
: текущий ( --> addr ) адрес объем MOD память + ;
: влево ( --> ) адрес 1 - TO адрес ;
: вправо ( --> ) адрес 1 + TO адрес ;
: прочесть ( --> flag ) текущий B@ 0<> ;
: изменить ( --> ) текущий B@ -1 XOR текущий B! ;[/pre]
вместо xxx подставить случайные числа, массив проинициализировать случайным содержимым. Размер любой в диапазоне от одной ячейки до 1 Гигабита. Обратите внимание на то, что адресация закольцована, т.е. перейдя последний бит попадаем в первый, и наоборот.

Если можно использовать слово текущий, то задача решается тривиально.
Иначе:
Методом вопроса задача решается за линейное время, но должно быть ограничение на макс. объём.
Без ограничения решается за квадратичное: пишем 1, затем пишем i нулей (i=1..бесконечность), возвращаемся на i бит и проверяем, жива ли 1.
Сообщение Добавлено: Чт июн 14, 2012 21:02
  Заголовок сообщения:  Re: *Помогите найти объем памяти  Ответить с цитатой
mOleg писал(а):
скажем, размер памяти - простое число


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


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

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

Если же объем не степень двойки, проверять придется после каждой записи единицы, возвращаясь назад... Да, придется побегать туда-сюда по памяти, если таки размер хочется знать.
Сообщение Добавлено: Чт июн 14, 2012 20:02
  Заголовок сообщения:  Re: *Помогите найти объем памяти  Ответить с цитатой
WingLion писал(а):
Читаем все остальное до предполагаемого предела - 1Гбита, проверяя, что все остальные данные повторяются. Если появляются неповторяющиеся данные - увеличивать N на единицу и снова на п.3.

Тут, возможно, есть та трудность, что данные с самого начала могут быть повторяющимися и именно так, чтобы дезориентировать решающего
Цитата:
а если размер бит?
ну мы обнулим его 2**30 раз, а после этого начав поиск по кругу, найдём на первом же шагу, определив объём памяти в 1 бит
Сообщение Добавлено: Чт июн 14, 2012 19:58
  Заголовок сообщения:  Re: *Помогите найти объем памяти  Ответить с цитатой
вопрос писал(а):
если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу

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

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

вот вот
ибо я чем дальше тем злее, могу начать зверствовать...
Сообщение Добавлено: Чт июн 14, 2012 19:49
  Заголовок сообщения:  это не решение задачи  Ответить с цитатой
вопрос писал(а):
если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу :ищем её, длина пути поиска и будет объём памяти

Теперь остается самая малость, написать программу с использованием
заданного в условии функционала. :)
Сообщение Добавлено: Чт июн 14, 2012 19:45

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


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