#include <stdio.h>
#define BITS 4
#define bin2gray(v) (v^(v>>1))
unsigned gray2bin1(unsigned v){
unsigned sum = v, length = BITS;
while(length > 0) v >>= 1, sum ^= v, length--;
return sum;
}
unsigned gray2bin2(unsigned v){
unsigned i;
for(i = 1; i < BITS; i <<= 1) v ^= (v >> i);
return v;
}
unsigned gray2bin3(unsigned v){
v ^= v >> 1;
v ^= v >> 2;
v ^= v >> 4;
v ^= v >> 8;
v ^= v >> 16;
return v;
}
/*----------------------------------------------------------------------*/
void printbits(unsigned v){
unsigned i; printf(" - ");
i = BITS; while(i > 0) printf("%u", (v >> --i) & 1);
}
int checkgray(unsigned i){
printf("%4u", i); printbits(i); printbits(bin2gray(i)); printf("\n");
if(i != gray2bin1(bin2gray(i)) ||
i != gray2bin2(bin2gray(i)) ||
i != gray2bin3(bin2gray(i))){
printf("%u: ®è¨¡ª* ¯¥à¥¢®¤* ¨§ ª®¤* ƒà¥ï!\n", i);
return 0;
}
return 1;
}
#define mostSignBit(bits) (1ul << (bits - 1))
#define maxUnsigned(bits) (mostSignBit(bits) | (mostSignBit(bits) - 1))
void main(){
unsigned i;
for(i = 0; checkgray(i) && i < (unsigned)maxUnsigned(BITS); i++);
}
Код грея [C]
Народ, подскажите, что надо изменить, чтоб программка работала так:
в коде грея перечислить все последовательности длины К из чисел 1...n
в коде грея перечислить все последовательности длины К из чисел 1...n
Код:
Трудно понять без комментариев какая переменная в проге отвечает K, а какая за n. В данном случае K=4?
Разве так можно писать while, как в функции gray2bin1()?
И ещё вопрос что напечатает printf("%u: ®è¨¡ª* ¯¥à¥¢®¤* ¨§ ª®¤* ƒà¥ï!\n", i);(так в проге написано)
Разве так можно писать while, как в функции gray2bin1()?
И ещё вопрос что напечатает printf("%u: ®è¨¡ª* ¯¥à¥¢®¤* ¨§ ª®¤* ƒà¥ï!\n", i);(так в проге написано)
Цитата: oltzowwa
Трудно понять без комментариев какая переменная в проге отвечает K, а какая за n. В данном случае K=4?
Разве так можно писать while, как в функции gray2bin1()?
И ещё вопрос что напечатает printf("%u: ®è¨¡ª* ¯¥à¥¢®¤* ¨§ ª®¤* ƒà¥ï!\n", i);(так в проге написано)
Разве так можно писать while, как в функции gray2bin1()?
И ещё вопрос что напечатает printf("%u: ®è¨¡ª* ¯¥à¥¢®¤* ¨§ ª®¤* ƒà¥ï!\n", i);(так в проге написано)
В алгоритме, нет ни "K" не "N", поэтому и прошу помочь, сейчас прога просто печатает последовательность возрастающую до 16.
Описание:"алгоритм перевода чисел в код Грея в позиционный код прост: каждый разряд в позиционном коде равен сумме по модулю 2 этого и всех более старших разрядов в коде Грея. Старшие разряды, соответственно, совпадают. На языке C это алгоритм может выглядеть так:
unsigned gray2bin(unsigned v){
unsigned sum = v, length = BITS;
while(length > 0) v >>= 1, sum ^= v, length--;
return sum;
}
Этот код является дословным переводом на язык C основного алгоритма, но его можно оптимизировать за счёт накопления промежуточных сумм в самом числе:
for(unsigned i = 1; i < BITS; i <<= 1) v ^= (v >> i);
Поскольку количество итераций здесь является уже логарифмом от числа бит и мало даже для очень больших чисел, то этот цикл лучше развернуть:
v ^= v >> 1; /* для 2-разрядных чисел */
v ^= v >> 2; /* для 4-разрядных чисел */
v ^= v >> 4; /* для 8-разрядных чисел */
v ^= v >> 8; /* для 16-разрядных чисел */
...
Перевод из позиционного кода в код Грея ещё проще: каждый разряд в коде Грея равен сумме по модулю 2 этого и следующего старшего разряда в позиционном коде. На языке C этот алгоритм реализуется выражением v^(v>>1)."
Цитата:
И ещё вопрос что напечатает printf("%u: ®è¨¡ª* ¯¥à¥¢®¤* ¨§ ª®¤* ƒà¥ï!\n", i);(так в проге написано)
а в проге написано следуещее: "ошибка перевода из кода Грея!\n".
собственно сама программа, которая
Цитата:
коде грея перечислить все последовательности длины К из чисел 1...n
вот:
Код:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void print_gray(unsigned char * massiv, unsigned int size)
{
for (int i=(size-1); i>=0; --i)
printf("%d",massiv);
};
void generate_gray(unsigned int n,unsigned int k)
{
unsigned char * gray_digit = (unsigned char *) malloc(sizeof(unsigned char)*k);
int i,p,j;
memset(gray_digit,0,sizeof(unsigned char)*k);
i = 0;
do
{
print_gray(gray_digit,k);
printf(" - :%d\n", i);
++i;
if(i>n)
break;
p=0;
j=i;
while ( j%2 == 0)
{
j = j/2;
++p;
};
if (p < k)
gray_digit = 1 - gray_digit;
}while( p < k );
free(gray_digit);
};
int main()
{
unsigned int k,n;
printf("Input k (bits length):");
scanf("%d",&k);
printf("Input n (num iteration):");
scanf("%d",&n);
generate_gray(n,k);
return 0;
}
#include <stdlib.h>
#include <string.h>
void print_gray(unsigned char * massiv, unsigned int size)
{
for (int i=(size-1); i>=0; --i)
printf("%d",massiv);
};
void generate_gray(unsigned int n,unsigned int k)
{
unsigned char * gray_digit = (unsigned char *) malloc(sizeof(unsigned char)*k);
int i,p,j;
memset(gray_digit,0,sizeof(unsigned char)*k);
i = 0;
do
{
print_gray(gray_digit,k);
printf(" - :%d\n", i);
++i;
if(i>n)
break;
p=0;
j=i;
while ( j%2 == 0)
{
j = j/2;
++p;
};
if (p < k)
gray_digit = 1 - gray_digit;
}while( p < k );
free(gray_digit);
};
int main()
{
unsigned int k,n;
printf("Input k (bits length):");
scanf("%d",&k);
printf("Input n (num iteration):");
scanf("%d",&n);
generate_gray(n,k);
return 0;
}
только смотри, если n больше чем 2^k, то код выводит только до 2^k (для следующий чисел k-битный код Грея просто неопределен).
я так погляжу у тебя прям тяга ко всяким рода последовательностям длинной k... =)
Одиссей, уже не в первый раз меня выручаешь! Спасибо! Ага, и вправду присутствует тяга к последовательностям длиной k :)
Объясни пожалуйста вот это место :
"while ( j%2 == 0)
{
j = j/2;
++p;
};
if (p < k)
gray_digit
Объясни пожалуйста вот это место :
"while ( j%2 == 0)
{
j = j/2;
++p;
};
if (p < k)
gray_digit
= 1 - gray_digit
;"
здесь вычисляется номер разряда p, который необходимо инвертировать.=)
Поставь рядом две последовательности (ну хотя бы для числа 3) в коде Грея и обычном двоичном и посмотри как меняется та и другая. Взаимосвязь видишь? Когда и где в первой меняется единица и где во второй инвертируется разряд.
Поставь рядом две последовательности (ну хотя бы для числа 3) в коде Грея и обычном двоичном и посмотри как меняется та и другая. Взаимосвязь видишь? Когда и где в первой меняется единица и где во второй инвертируется разряд.