ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный код Фибоначчи
25 сообщений из 51, страница 1 из 3
  1  все
Тяпничный код Фибоначчи
    #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, 16:27
| Ответить | Цитировать | Написать  
Тяпничный код Фибоначчи
    #39993532
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

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

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

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

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


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

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

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

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

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

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

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

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

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

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

Думаю, не стоит заморачиваться на логарифмический поиск старшего разряда, потому что потом все равно придется заполнять другие разряды, и в сумме у нас всё равно будет линейное время.
...
Рейтинг: 0 / 0
29.08.2020, 08:31
| Ответить | Цитировать | Написать  
Тяпничный код Фибоначчи
    #39994505
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
UP. Пора подводить неутешительные итоги. Никто неосилил. И я неосилил.
...
Рейтинг: 0 / 0
01.09.2020, 15:02
| Ответить | Цитировать | Написать  
Тяпничный код Фибоначчи
    #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:21
| Ответить | Цитировать | Написать  
Тяпничный код Фибоначчи
    #39994526
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Имя пользователя1, шикарно.

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

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

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

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

Или не надо кодировать?
можешь просто дописать нулей в конец, они не повлияют
...
Рейтинг: 0 / 0
01.09.2020, 15:46
| Ответить | Цитировать | Написать  
Тяпничный код Фибоначчи
    #39994538
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да пожалуй не надо. Это в криптографии всякий Padding нужны. А в нашем случае просто последний единичный бит.
...
Рейтинг: 0 / 0
01.09.2020, 15:57
| Ответить | Цитировать | Написать  
Тяпничный код Фибоначчи
    #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:24
| Ответить | Цитировать | Написать  
Тяпничный код Фибоначчи
    #39994720
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Признак конца битового потока все таки нужен.

Иначе мы не сможем определить " пустой поток "
...
Рейтинг: 0 / 0
02.09.2020, 11:39
| Ответить | Цитировать | Написать  
25 сообщений из 51, страница 1 из 3
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный код Фибоначчи
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39993567&tid=1339743]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 180ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 67ms
get tp. blocked users:
 2ms
others: 15ms
total:  307ms
созд. / загр.: 307ms
x
x
Закрыть


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