Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
mishkazzz
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 34
#1

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

28.03.2014, 23:05. Просмотров 639. Ответов 13
Метки нет (Все метки)

добрый вечер!

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

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

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

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

Из массива сформировать непрерывную последовательность положительных чисел с наибольшей суммой - C++
Приветствую всех!!! Благодарен, тому кто ответит!!! Сделать массив из 10-и элементов и сгенерировать его от -25 до 50. На основе...

Найти ту непрерывную последовательность положительных чисел, сумма элементов которой максимальна - C++
Найти ту непрерывную последовательность положительных чисел, сумма элементов в которой максимальная

Найти непрерывную последовательность положительных чисел, сумма элементов которой максимальна - C++
Знайти таку нерозривну послыдовнысть позитивних чисел сума елементыв якый максимальна

Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна - C++
В произвольном массиве нужно найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна. ...

Повторяющуюся последовательность символов заменить своим кодом - C++
Для задания использовать строки массива типа char Дана строка символов. Для сохранения ее в сжатом виде найти максимальную...

если в строке встречена одинаковая последовательность символов, заменить их кодом 255 - C++
Задача такова: обработать массив строк (длина каждой не более 100 символов). если в строке встречена одинаковая последовательность...

13
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,188
28.03.2014, 23:26 #2
Цитата Сообщение от mishkazzz Посмотреть сообщение
бита отводятся под количество кодируемых символов, а последний - под объект кодирования(то есть четыре подряд идущих единицы должны кодироваться , как 00111)
можа я ничего не понимаю но по моему 11 это 3 а никак не 4
Цитата Сообщение от mishkazzz Посмотреть сообщение
е могу понять, как завести 5-битную переменную и как после этого считывать блоками именно по 5 бит?
никак
Си не поддерживает работу с битами( ну кроме битовых операций "и" "или" "не" "исключающие или")
есть два пути
упаковка своих слов(5бит) в стандартные переменные
или создать свой тип данных например массив из 5 байт
Цитата Сообщение от mishkazzz Посмотреть сообщение
из/в файл(-ов)
как в файле представлены пятибитные слова?

и если например мне придет число 11111 это сколько единиц 15 или 16 и как они уложатся в пятибитный формат?
0
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
28.03.2014, 23:47 #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));
Как-то так. Скобок наставил, ибо не помню приоритетов.
1
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,188
28.03.2014, 23:58 #4
Цитата Сообщение от Байт Посмотреть сообщение
Не совсем так. Вот кусок из qwidget.h
ну ты же понимаешь что это костыли
теперь как положить 1 слово(5 байт) 2..... 100
как структуру опишешь
по большому счету и процессоры с таким форматом не могут работать
Цитата Сообщение от Байт Посмотреть сообщение
Пусть есть массив char B[200], рассматриваемый как массив из 1600 битов
Извлечение n-го бита:
все б было хорошо но 5 байтов не кратно 8
о чем я и говорил
Цитата Сообщение от ValeryS Посмотреть сообщение
упаковка своих слов(5бит) в стандартные переменные
выигрываем в памяти проигрываем в скорости

в общем задача не тривиальная, и чтобы её решить нужно еще кучу данных
0
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
29.03.2014, 00:09 #5
Цитата Сообщение от ValeryS Посмотреть сообщение
все б было хорошо но 5 байтов не кратно 8
А и не надо. По одному битику, аккуратнЕнько

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

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

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

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

Добавлено через 6 минут
видимо дело именно в том, что нужно превратить все это в "бинарный файл", что явно не то, о чем я думал
может быть кто-нибудь знает, где почитать хорошо разжеванный материал по этой теме?
0
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
31.03.2014, 11:54 #7
Цитата Сообщение от mishkazzz Посмотреть сообщение
то есть четыре подряд идущих единицы должны кодироваться , как 00111)
Значит здесь все-таки ошибка. 1111 -> 01001, 000000 -> 01100 Так?
Чтобы тебе помочь надо получить представление о том, что именно тебе непонятно. Покажи свои попытки, наброски кода, с комментариями типа, "а вот тут хочу сделать то-то, но не знаю как.
Желательно в виде прикрепленного файла (лично мне так удобнее разбираться).
На мой взгляд тут самое тонкое место - преобразование последовательности битов в массив char-ов. Технику этого дела я набросал в посте #3
0
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,188
31.03.2014, 12:24 #8
Цитата Сообщение от mishkazzz Посмотреть сообщение
в первых 4 битах лежит повторитель, указывающий, сколько раз данный символ повторяется. если повторитель равен 0,
а если нужен одна 1 или 0 ???
как закодировать вот такую последовательность 10101010101010
0
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
31.03.2014, 12:34 #9
Цитата Сообщение от ValeryS Посмотреть сообщение
такую последовательность 10101010101010
Видимо, 0000100000 и так еще 6 раз
0
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,188
31.03.2014, 12:50 #10
Цитата Сообщение от Байт Посмотреть сообщение
Видимо, 0000100000
да но количество повторов 0000 противоречит с этим
Цитата Сообщение от mishkazzz Посмотреть сообщение
если повторитель равен 0, достигнут конец файла.
мне вообше странно откуда эти 5 байт выплыли
такое ощущение что последовательность передают по com порту с пятибайтным форматом
0
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
31.03.2014, 14:04 #11
Цитата Сообщение от Байт Посмотреть сообщение
Видимо, 0000100000 и так еще 6 раз
ошибочка моя, извините. Следует читать 0000100010

Добавлено через 1 минуту
Цитата Сообщение от ValeryS Посмотреть сообщение
с пятибайтным форматом
Наверное, хотел сказать - пятибитным
Цитата Сообщение от ValeryS Посмотреть сообщение
такое ощущение что последовательность передают по com порт
А что? Вполне возможно...
2
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,188
31.03.2014, 14:43 #12
Цитата Сообщение от Байт Посмотреть сообщение
0000100010
опять в последовательности единиц количество 0
может так
0001100010
но тогда 4 единицы не 00111 а 01001
т.е количество а не количество минус 1
Цитата Сообщение от Байт Посмотреть сообщение
Наверное, хотел сказать - пятибитным
ну да
Биты Байты постоянно путаюсь, причем понимать понимаю начинаю писать обязательно попутаю
2
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
31.03.2014, 15:10 #13
Цитата Сообщение от ValeryS Посмотреть сообщение
опять в последовательности единиц количество 0
может так 0001100010
Да, конечно! Опять напутал. Видать день такой, канун 1-го апреля )
Цитата Сообщение от ValeryS Посмотреть сообщение
тогда 4 единицы не 00111 а 01001
На это я уже обратил внимание ТС
0
mishkazzz
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 34
03.04.2014, 13:46  [ТС] #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
декодирует тоже посимвольно
0
03.04.2014, 13:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.04.2014, 13:46
Привет! Вот еще темы с ответами:

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

найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Нужно найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. В чем ошибка ? #include &lt;iostream&gt; #include...

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. Входные данные: В единственной строке...

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Здравствуйте, не могу понять в чём может быть ошибка :) Решаю олимпиадную задачу. Но система находит в тесте 5 не верный ответ) В...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru