Гость
Войти | Профиль | Очистить
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный код Фибоначчи / 25 сообщений из 51, страница 1 из 3
  1  все
28.08.2020, 16:27
    #39993507
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Привет котаны!

Числа фибоначчи (Ф) это такая sequence:
Код: plaintext
1,1,2,3,5,8,13....
e.t.c.

Если считать эти числа - весами разрядов в некой позиционной системе - то получаем систему наподобие двоичной.

Табличка.
NumberFiller12358131*12*13*14*115*16*117*118*19*1110*1111*1112*11113*11

Эта система обладает таким свойством. В ней нет двух подряд идущих единичек. Если
есть единички в разрядах 1 и 2 - то они немедленно суммируются и передаются в следующий разряд.

Символ "*" я ввел искусственно. Чуть ниже я объясню зачем.

Можно даже сделать механический счетчик на такой системе который будет делать инкремент
на каждое воздействие.

Задача 1

Необходимо сделать такой кодек чтоб на вход шла последовательность любых целых чисел начиная от 1 а на выходе - последовательность бит в системе Ф.

Здесь символ "*" я спокойно заменил на "1" без потерь свойства различимости этого потока.

Пример.

Input:
Код: sql
1.
1,2,3,4,12,13



Output:
Код: sql
1.
1110110011101101011000001



Здесь первые 2 символа "11" - это филлер и единичка. Тоесть число 1.
Следующее число - "101" - это число 2.

Можно output сделать в виде string и задача формально решена.
Числа могут иметь вобщем любую разрядность.

Задача 2

Сделать обратную задачу. Декодер.

С пятницей всех.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:10
    #39993532
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton,

ммм...
а "числа" во входном потоке это кто?

если это что-то похожее на настоящие целые "числа" фиксированной разрядности,
то вроде бы не должно быть больших проблем,
поскольку массив на фиксированное число "разрядов фибоначчи" не требует вычисления и его можно считать бессплатным...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:21
    #39993539
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Вот еще пример. Число побольше.

Код: plaintext
1.
1,2,3,4,12,13,5555555555, 99999999999999
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:28
    #39993541
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton,

а вот это число или что 999999999999999‭999999999999999999‬?
о какой компьютерной математике, оперирующей "числами" идет речь?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:37
    #39993546
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Буби. С пятницей тебя. Ты чего такой сердитый?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:40
    #39993552
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton
Буби. С пятницей тебя. Ты чего такой сердитый?


с чего вдруг сердитый, я пятнице радусь.
я почти совершенно счастлив, а ты про числа рассказать всё не хочешь.
Тебя тоже с пятницей.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:42
    #39993553
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Твой вопрос касается ограничений?

Ограничение - int64.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:43
    #39993555
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton
Твой вопрос касается ограничений?

Ограничение - int64.

во, это дело.
щаз я уже весь в пятнице, но чую, не должно быть там ничего военного.
может вечером или в ночи, освободясь от пятницы...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:46
    #39993556
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Ну давай. Декодирование - чуть похитрее будет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 17:49
    #39993558
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Поправил табличку.

NumberFiller12358131*12*13*14*115*16*117*118*19*1110*1111*1112*11113*1
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 18:02
    #39993567
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Правильно ли я понимаю, что выходом кодирования должна являться "бинарная строка" - последовательность байт,
сама по себе "числом" в смысле int64, или даже просто строка,
и оно приходит на вход "декодирования"?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 18:03
    #39993568
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Да.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 18:37
    #39993588
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton
Ограничение - int64.

навскидку не вижу ничего подвохообразного.
имеем на руках массив порядка 100 чисел Фибоначчи.
при кодировании находим максимальное число Ф не более заданного, ставим единицу в соответствующий разряд, вычитаем найденное из заданного, кодируем остаток. Поиск числа можно бинарным поиском, но на 100 элементах ускорение не сильное.

декодирование ещё проще - обходим наши нули-единицы, и там где 1, добавляем в копилку соответствующее разряду число Ф, беря его из массива по индексу.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 18:45
    #39993595
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
А нужен-ли нам массив?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.08.2020, 19:14
    #39993616
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton
А нужен-ли нам массив?
да в принципе нет. Для кодирования ищем число Ф, от меньшего к большему, это можно линейно делать с двумя вспомогательными переменными. Для декодирования опять же, смотрим разряды от младшего, и попутно накручиваем числа Ф, тоже двумя переменными.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.08.2020, 00:59
    #39993706
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton
А нужен-ли нам массив?

(пятница меня победила, так что кодирования пока не будет)

массив позволит за логарифм от максимального кодируемого числа M найти старший разряд,
после чего спускаться линейно по кодируемуму n к младшему.
Без массива стоит вопрос - какова степень для первого фиб. числа, превышающего кодируемое.
я не знаю, как в таком случае закодировать меньше, чем за 2n по отношению к кодируемуму n

что лучше - зависит от статистики входного потока.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.08.2020, 02:03
    #39993711
ВсеРазумный
ВсеРазумный
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
По теме
https://en.wikiversity.org/wiki/Fibonacci_sequences,_binary_numbers_and_compositions
https://en.wikipedia.org/wiki/Fibonacci_coding
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.08.2020, 08:31
    #39993732
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
booby,

Думаю, не стоит заморачиваться на логарифмический поиск старшего разряда, потому что потом все равно придется заполнять другие разряды, и в сумме у нас всё равно будет линейное время.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2020, 15:02
    #39994505
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
UP. Пора подводить неутешительные итоги. Никто неосилил. И я неосилил.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2020, 15:21
    #39994515
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
вот, за 5 минут на коленке
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
function encodeF(n) {
    var a = 1, b = 1, t, r, len = 0;
    while (b <= n) {
        t = a + b;
        a = b;
        b = t;
        len++;
    }
    r = new Array(len--);
    while(b) {
        t = b - a;
        b = a;
        a = t;
        if (b <= n) {
            r[len] = 1;
            n -= b;
        } else {
            r[len] = 0;
        }
        len--;
    }
    return r.join('');
}

function decodeF(n) {
    var a = 1, b = 1, t, sum = 0;
    for (var i = 0; i < s.length; ++i) {
        if (s[i] === '1') {
            sum += b;
            t = a + b;
            a = b;
            b = t;
        }
    }
    return sum;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2020, 15:42
    #39994526
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Имя пользователя1, шикарно.

Я протестирую чуть позже.

+Мне еще надо будет реализовать нечто вроде бинарного writer для этой системы.

И придумать как правильно закодировать хвостик. Последние несколько бит кратных WORD (int).

Или не надо кодировать?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2020, 15:46
    #39994530
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
mayton
И придумать как правильно закодировать хвостик. Последние несколько бит кратных WORD (int).

Или не надо кодировать?
можешь просто дописать нулей в конец, они не повлияют
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2020, 15:57
    #39994538
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Да пожалуй не надо. Это в криптографии всякий Padding нужны. А в нашем случае просто последний единичный бит.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.09.2020, 11:24
    #39994716
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Имя пользователя1
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function decodeF(n) {
    var a = 1, b = 1, t, sum = 0;
    for (var i = 0; i < s.length; ++i) {
        if (s[i] === '1') {
            sum += b;
            t = a + b;
            a = b;
            b = t;
        }
    }
    return sum;
}

поправка, не то забрал из консоли браузера)
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function decodeF(s) {
    var a = 1, b = 1, t, sum = 0;
    for (var i = 0; i < s.length; ++i) {
        if (s[i] === '1') {
            sum += b;
        }
        t = a + b;
        a = b;
        b = t;
    }
    return sum;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.09.2020, 11:39
    #39994720
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный код Фибоначчи
Признак конца битового потока все таки нужен.

Иначе мы не сможем определить " пустой поток "
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный код Фибоначчи / 25 сообщений из 51, страница 1 из 3
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 517ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1339743]:
 0ms
get settings:
 10ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 177ms
get topic data:
 12ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 236ms
total:  517ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]