Автор |
Сообщение |
|
|
Заголовок сообщения: |
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. Задачу можно усложнить поставив в условии требование о сохранении исходного содержимого памяти.
[code]\ симулятор
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[/code]log [code]9053092 17170468 26223560 24377646 \ объем нач. адрес кон. адрес текущий адрес 9053092 \ результат Ok[/code] 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 ;
[code]: сколькобит ( --> # ) 0x80000000 0 DO прочесть IF изменить THEN вправо LOOP прочесть 0= IF изменить THEN 0x80000000 0 DO прочесть IF I 1+ LEAVE THEN вправо LOOP ;[/code] Ps. Вариант с неизвестным пределом объема памяти не рассматриваю, так как он не имеет смысла с чисто вычислительной стороны. Решать вариант с известным пределом объема памяти с возвратом(2 алгоритм от dinamic-wind) тоже особого смысла нет, так как даже при малом объеме памяти он проигрывает по времени счета приведенному решению. Да, забыл. Решение на манипуляторах будет выглядеть так: [code]: сколькобит ( --> # ) 0x80000000 0 ['] прочесть ['] изменить ['] вправо 5\01D2Xi3Xt4XL2XZi3Xt01D2XiI`1+Qt4XL ;[/code]
|
|
|
|
Добавлено: Пт июн 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.
[quote="mOleg"] : текущий ( --> addr ) адрес объем MOD память + ; : влево ( --> ) адрес 1 - TO адрес ; : вправо ( --> ) адрес 1 + TO адрес ; : прочесть ( --> flag ) текущий B@ 0<> ; : изменить ( --> ) текущий B@ -1 XOR текущий B! ;[/pre] вместо xxx подставить случайные числа, массив проинициализировать случайным содержимым. Размер любой в диапазоне от одной ячейки до 1 Гигабита. Обратите внимание на то, что адресация закольцована, т.е. перейдя последний бит попадаем в первый, и наоборот.[/quote] Если можно использовать слово [b]текущий[/b], то задача решается тривиально. Иначе: Методом [b]вопрос[/b]а задача решается за линейное время, но должно быть ограничение на макс. объём. Без ограничения решается за квадратичное: пишем 1, затем пишем i нулей (i=1..бесконечность), возвращаемся на i бит и проверяем, жива ли 1.
|
|
|
|
Добавлено: Чт июн 14, 2012 21:02 |
|
|
|
|
|
Заголовок сообщения: |
Re: *Помогите найти объем памяти |
|
|
mOleg писал(а): скажем, размер памяти - простое число Надо было предупреждать в условии, что память инопланетянская. вопрос писал(а): Тут, возможно, есть та трудность, что данные с самого начала могут быть повторяющимися и именно так, чтобы дезориентировать решающего Тогда второй вариант с записью последовательных чисел, начиная с нуля, пока первый ноль не затрется. Однобитный вариант обнаружится сразу, потому что на уже на втором бите единичка затрет первый нолик. Собственно, сохранять содержимое в условии не сказано, поэтому просто пишем нули, проверяя, что запись единичкс, записанная в адрес 2^N с целыми N не попадает в нулевой адрес... Если же объем не степень двойки, проверять придется после каждой записи единицы, возвращаясь назад... Да, придется побегать туда-сюда по памяти, если таки размер хочется знать.
[quote="mOleg"]скажем, размер памяти - простое число [/quote]
Надо было предупреждать в условии, что память инопланетянская.
[quote="вопрос"]Тут, возможно, есть та трудность, что данные с самого начала могут быть повторяющимися и именно так, чтобы дезориентировать решающего[/quote] Тогда второй вариант с записью последовательных чисел, начиная с нуля, пока первый ноль не затрется. Однобитный вариант обнаружится сразу, потому что на уже на втором бите единичка затрет первый нолик. Собственно, сохранять содержимое в условии не сказано, поэтому просто пишем нули, проверяя, что запись единичкс, записанная в адрес 2^N с целыми N не попадает в нулевой адрес...
Если же объем не степень двойки, проверять придется после каждой записи единицы, возвращаясь назад... Да, придется побегать туда-сюда по памяти, если таки размер хочется знать.
|
|
|
|
Добавлено: Чт июн 14, 2012 20:02 |
|
|
|
|
|
Заголовок сообщения: |
Re: *Помогите найти объем памяти |
|
|
WingLion писал(а): Читаем все остальное до предполагаемого предела - 1Гбита, проверяя, что все остальные данные повторяются. Если появляются неповторяющиеся данные - увеличивать N на единицу и снова на п.3. Тут, возможно, есть та трудность, что данные с самого начала могут быть повторяющимися и именно так, чтобы дезориентировать решающего Цитата: а если размер бит? ну мы обнулим его 2**30 раз, а после этого начав поиск по кругу, найдём на первом же шагу, определив объём памяти в 1 бит
[quote="WingLion"]Читаем все остальное до предполагаемого предела - 1Гбита, проверяя, что все остальные данные повторяются. Если появляются неповторяющиеся данные - увеличивать N на единицу и снова на п.3.[/quote] Тут, возможно, есть та трудность, что данные с самого начала могут быть повторяющимися и именно так, чтобы дезориентировать решающего [quote]а если размер бит?[/quote] ну мы обнулим его 2**30 раз, а после этого начав поиск по кругу, найдём на первом же шагу, определив объём памяти в 1 бит
|
|
|
|
Добавлено: Чт июн 14, 2012 19:58 |
|
|
|
|
|
Заголовок сообщения: |
Re: *Помогите найти объем памяти |
|
|
вопрос писал(а): если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу а если размер бит? а до гига диапазон лишь в тесте, может там 16 Гбит, или 256? а может 3 бита А нужно точно знать, сколько chess писал(а): Теперь остается самая малость, написать программу с использованием заданного в условии функционала. вот вот ибо я чем дальше тем злее, могу начать зверствовать...
[quote="вопрос"]если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу[/quote] а если размер бит? а до гига диапазон лишь в тесте, может там 16 Гбит, или 256? а может 3 бита 8) А нужно точно знать, сколько 8)
[quote="chess"]Теперь остается самая малость, написать программу с использованием заданного в условии функционала.[/quote] вот вот ибо я чем дальше тем злее, могу начать зверствовать...
|
|
|
|
Добавлено: Чт июн 14, 2012 19:49 |
|
|
|
|
|
Заголовок сообщения: |
это не решение задачи |
|
|
вопрос писал(а): если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу :ищем её, длина пути поиска и будет объём памяти Теперь остается самая малость, написать программу с использованием заданного в условии функционала.
[quote="вопрос"]если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу :ищем её, длина пути поиска и будет объём памяти [/quote] Теперь остается самая малость, написать программу с использованием заданного в условии функционала. :)
|
|
|
|
Добавлено: Чт июн 14, 2012 19:45 |
|
|
|
|