Форум программистов, компьютерный форум CyberForum.ru

Непрерывную последовательность 0 и 1 закодировать 5-битным кодом - C++

Восстановить пароль Регистрация
 
mishkazzz
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 34
28.03.2014, 23:05     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #1
добрый вечер!

столкнулся с проблемой в задаче, сама задача состоит в следующем:

непрерывную последовательность 0 и 1 закодировать 5-битным кодом, где 4 первых бита отводятся под количество кодируемых символов, а последний - под объект кодирования(то есть четыре подряд идущих единицы должны кодироваться , как 00111)

нужно написать кодирование и раскодирование, ввод/вывод происходит из/в файл(-ов)

не могу понять, как завести 5-битную переменную и как после этого считывать блоками именно по 5 бит?
с самим пониманием, как это все должно выглядеть, проблем нет (там вроде сам процесс в простенький двойной цикл укладывается)
заранее спасибо за помощь!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.03.2014, 23:05     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом
Посмотрите здесь:

C++ если в строке встречена одинаковая последовательность символов, заменить их кодом 255
Закодировать входную строку алгоритмом сокращения повторяющихся символов. C++
найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц
Закодировать и сохранить закодированый текст в файл C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,053
28.03.2014, 23:26     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #2
Цитата Сообщение от mishkazzz Посмотреть сообщение
бита отводятся под количество кодируемых символов, а последний - под объект кодирования(то есть четыре подряд идущих единицы должны кодироваться , как 00111)
можа я ничего не понимаю но по моему 11 это 3 а никак не 4
Цитата Сообщение от mishkazzz Посмотреть сообщение
е могу понять, как завести 5-битную переменную и как после этого считывать блоками именно по 5 бит?
никак
Си не поддерживает работу с битами( ну кроме битовых операций "и" "или" "не" "исключающие или")
есть два пути
упаковка своих слов(5бит) в стандартные переменные
или создать свой тип данных например массив из 5 байт
Цитата Сообщение от mishkazzz Посмотреть сообщение
из/в файл(-ов)
как в файле представлены пятибитные слова?

и если например мне придет число 11111 это сколько единиц 15 или 16 и как они уложатся в пятибитный формат?
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
28.03.2014, 23:47     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #3
Цитата Сообщение от ValeryS Посмотреть сообщение
Си не поддерживает работу с битами
Не совсем так. Вот кусок из qwidget.h
C++
1
2
3
4
5
    uint window_state : 4;
    uint focus_policy : 4;
    uint sizehint_forced :1;
    uint is_closing :1;
    uint in_show : 1;
Но, ИМХО, логичнее использовать массив байтов и операции >>, << & ~
Щас попробую набросать...

Добавлено через 1 минуту
Цитата Сообщение от ValeryS Посмотреть сообщение
можа я ничего не понимаю но по моему 11 это 3 а никак не 4
Наверное, логично в 1-е 4 бита записывать именно k-1

Добавлено через 8 минут
Пусть есть массив char B[200], рассматриваемый как массив из 1600 битов
Извлечение n-го бита:
C++
1
2
3
i = n/8;
j = n%8;
return ((B[i] >> j) & 1);
Установка n-го бита в x (0 или 1)
C++
1
B[i] = ((B[i] & (~(1<<j))) | (x<<j));
Как-то так. Скобок наставил, ибо не помню приоритетов.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,053
28.03.2014, 23:58     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #4
Цитата Сообщение от Байт Посмотреть сообщение
Не совсем так. Вот кусок из qwidget.h
ну ты же понимаешь что это костыли
теперь как положить 1 слово(5 байт) 2..... 100
как структуру опишешь
по большому счету и процессоры с таким форматом не могут работать
Цитата Сообщение от Байт Посмотреть сообщение
Пусть есть массив char B[200], рассматриваемый как массив из 1600 битов
Извлечение n-го бита:
все б было хорошо но 5 байтов не кратно 8
о чем я и говорил
Цитата Сообщение от ValeryS Посмотреть сообщение
упаковка своих слов(5бит) в стандартные переменные
выигрываем в памяти проигрываем в скорости

в общем задача не тривиальная, и чтобы её решить нужно еще кучу данных
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
29.03.2014, 00:09     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #5
Цитата Сообщение от ValeryS Посмотреть сообщение
все б было хорошо но 5 байтов не кратно 8
А и не надо. По одному битику, аккуратнЕнько

Добавлено через 1 минуту
Цитата Сообщение от ValeryS Посмотреть сообщение
выигрываем в памяти проигрываем в скорости
Таки это смысл любой упаковки...

Добавлено через 2 минуты
Ладно. Подождем, когда ТС проснется. У меня такое ощущенье, что что-то у него по нашим наброскам может получиться.
mishkazzz
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 34
30.03.2014, 23:21  [ТС]     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #6
Байт, ValeryS, кину полный текст задачи, потому что то, что вы предлагаете - явно выше моего уровня, но я постараюсь в этом разобраться

большое спасибо за ваши ответы!

итак, текст задачи:
"Исходные данные записаны в файл в виде непрерывной последовательности 0 и 1. написать программу конвертор, которая исходный текстовый файл преобразует в бинарный файл в следующем формате. бинарный файл состоит из записей по 5 бит, расположенных впритык друг к другу. каждая запись кодирует набор одинаковых подряд идущих символов исходного файла. последний бит записи указывает, какой символ кодируется - 0 или 1, а в первых 4 битах лежит повторитель, указывающий, сколько раз данный символ повторяется. если повторитель равен 0, достигнут конец файла. написать раскодировщик"

Добавлено через 6 минут
видимо дело именно в том, что нужно превратить все это в "бинарный файл", что явно не то, о чем я думал
может быть кто-нибудь знает, где почитать хорошо разжеванный материал по этой теме?
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
31.03.2014, 11:54     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #7
Цитата Сообщение от mishkazzz Посмотреть сообщение
то есть четыре подряд идущих единицы должны кодироваться , как 00111)
Значит здесь все-таки ошибка. 1111 -> 01001, 000000 -> 01100 Так?
Чтобы тебе помочь надо получить представление о том, что именно тебе непонятно. Покажи свои попытки, наброски кода, с комментариями типа, "а вот тут хочу сделать то-то, но не знаю как.
Желательно в виде прикрепленного файла (лично мне так удобнее разбираться).
На мой взгляд тут самое тонкое место - преобразование последовательности битов в массив char-ов. Технику этого дела я набросал в посте #3
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,053
31.03.2014, 12:24     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #8
Цитата Сообщение от mishkazzz Посмотреть сообщение
в первых 4 битах лежит повторитель, указывающий, сколько раз данный символ повторяется. если повторитель равен 0,
а если нужен одна 1 или 0 ???
как закодировать вот такую последовательность 10101010101010
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
31.03.2014, 12:34     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #9
Цитата Сообщение от ValeryS Посмотреть сообщение
такую последовательность 10101010101010
Видимо, 0000100000 и так еще 6 раз
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,053
31.03.2014, 12:50     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #10
Цитата Сообщение от Байт Посмотреть сообщение
Видимо, 0000100000
да но количество повторов 0000 противоречит с этим
Цитата Сообщение от mishkazzz Посмотреть сообщение
если повторитель равен 0, достигнут конец файла.
мне вообше странно откуда эти 5 байт выплыли
такое ощущение что последовательность передают по com порту с пятибайтным форматом
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
31.03.2014, 14:04     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #11
Цитата Сообщение от Байт Посмотреть сообщение
Видимо, 0000100000 и так еще 6 раз
ошибочка моя, извините. Следует читать 0000100010

Добавлено через 1 минуту
Цитата Сообщение от ValeryS Посмотреть сообщение
с пятибайтным форматом
Наверное, хотел сказать - пятибитным
Цитата Сообщение от ValeryS Посмотреть сообщение
такое ощущение что последовательность передают по com порт
А что? Вполне возможно...
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,053
31.03.2014, 14:43     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #12
Цитата Сообщение от Байт Посмотреть сообщение
0000100010
опять в последовательности единиц количество 0
может так
0001100010
но тогда 4 единицы не 00111 а 01001
т.е количество а не количество минус 1
Цитата Сообщение от Байт Посмотреть сообщение
Наверное, хотел сказать - пятибитным
ну да
Биты Байты постоянно путаюсь, причем понимать понимаю начинаю писать обязательно попутаю
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
31.03.2014, 15:10     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #13
Цитата Сообщение от ValeryS Посмотреть сообщение
опять в последовательности единиц количество 0
может так 0001100010
Да, конечно! Опять напутал. Видать день такой, канун 1-го апреля )
Цитата Сообщение от ValeryS Посмотреть сообщение
тогда 4 единицы не 00111 а 01001
На это я уже обратил внимание ТС
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.04.2014, 13:46     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом
Еще ссылки по теме:

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
C++ Как закодировать методом циклического сдвига?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
mishkazzz
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 34
03.04.2014, 13:46  [ТС]     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом #14
ValeryS, Байт, сейчас скину свой код, но он является обманом, потому как пишет просто 0 и 1 именно числами

насколько я понял, тут нужно использовать что-то вроде
C++
1
2
3
4
struct code {
unsigned amount : 4;
unsigned symbol : 1;
}
мой код работает по-другому, и, собственно, мне сказали, что биты я как таковые не использую
то есть файл с кодом должен весить столько бит, сколько в нем символов
поможет ли мне в этом расширение .bin?

спасибо вам большое за помощь
ниже прилагаю свой код
C++
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
 
using namespace std;
 
int transmute(char c)
{
    if(c=='1') return 1;
    if(c=='0') return 0;
    else return -1;
}
 
void encode(FILE *fin, FILE *fout)
{
    char c;
    char t;
    int temp;
    int num=0;
    int prev;
    int cur;
    int helptool;
    int del;
    fscanf(fin, "%c", &c);
    prev=transmute(c);
    num++;
    while(fscanf(fin, "%c", &c)==1)
    {
            cur=transmute(c);
            if(prev==cur)
            {
            num++;
                    if(num==15)
                    {
                        fprintf(fout, "1111x%d\n", cur);
                        num=0;
                    }
            }
            else
            {
                del=8;
                for(int i=0; i<4; i++)
                {
                    if(num>=del)
                    {
                        fprintf(fout, "1");
                        num=num-del;
                        del=del/2;
                    }
                    else
                    {
                        fprintf(fout, "0");
                        del=del/2;
                    }
                }
            fprintf(fout, "x%d\n", prev);
            prev=cur;
            num=1;
            }
    }
        if(num>0)
        {
            del=8;
                for(int i=0; i<4; i++)
                {
                    if(num>=del)
                    {
                        fprintf(fout, "1");
                        num=num-del;
                        del=del/2;
                    }
                    else
                    {
                        fprintf(fout, "0");
                        del=del/2;
                    }
                }
            fprintf(fout, "x%d\n", prev);
        }
 
fprintf(fout, "0000x0");
}
 
 
void decode(FILE *fin, FILE *fout)
{
    int checker=1;
    int num=0;
    char c;
    int temp;
    int mult=8;
 
 
    while(checker!=0)
    {
        for(int i=0; i<4; i++)
        {
            fscanf(fin, "%c", &c);
            temp=transmute(c);
            num=num+mult*temp;
            mult=mult/2;
        }
        if(num==0) {checker=0;}
        else
        {
            fscanf(fin, "%c", &c); // pudtoe schityvanie
            fscanf(fin, "%c", &c);
            temp=transmute(c);
            fscanf(fin, "%c", &c); // pustoe schityvanie
            for(int j=0; j<num; j++)
            {
                fprintf(fout, "%d", temp);
            }
        num=0;
        mult=8;
        }
    }
 
}
 
int main()
{
   FILE *f1, *f2;
f1=fopen("input.txt", "r");
f2=fopen("output.txt", "w");
encode(f1, f2);
fclose(f1);
fclose(f2);
 
f1=fopen("output.txt", "r");
f2=fopen("checktheinput.txt", "w");
decode(f1, f2);
fclose(f1);
fclose(f2);
return 0;
}

он работает следующим образом:

кодирует 000, к примеру, как 0011x0
декодирует тоже посимвольно
Yandex
Объявления
03.04.2014, 13:46     Непрерывную последовательность 0 и 1 закодировать 5-битным кодом
Ответ Создать тему
Опции темы

Текущее время: 07:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru