推 cbscloud:謝謝~! 11/14 08:02
※ 引述《cbscloud (v想做的事快點完成)》之銘言：
: 請問一下有什麼好方法可以找出gray code
: 1 2 3
: 2bit 3bit 4bit
: 00 000 0000
: 01 001 0001
: 10 010 0010
: 11 011 0011
: 111 0111
: 110 0110
: 101 0101
: 100 0100
: 1100
: 1101
: 1110
: 1111
: 1011
: 1010
: 1001
: 1000
: 請問一下之後要怎麼分別出gray code
: 上課有教兩兩相鄰,只有一個bit不一樣,其他bit都一
: 樣(且為2的倍數)
: 可是我用這個方法 有點怪怪的
: 不知道有沒有其他高手可以幫我解說一下~!
: 謝謝~!
這種問題是Combinatorial Generation產生組合的問題的一種，
你可以在Frank Ruskey's Combinatorial Generation Resources網站，
找到這類的演算法與程式碼。
http://www.cs.sunysb.edu/~algorith/implement/ruskey/implement.shtml
在此把產生Gray Code的範例程式貼於下供您參考：
/* Gray Code Generation Algorithm Example
*
----------------------------------------------------------------------------
*/
#include <stdio.h>
#include <stdlib.h>
/* specify the algorithm used (0 = recursive, 1 = iterative) */
#define GRAY_ALG 1
/* globals - accessed by sequence generation functions */
int *sequence; /* array containing the sequence for output */
int slength; /* sequence length */
/* --- seq_out() ---
* Output the sequence array.
*/
void seq_out() {
int i;
printf("%d", sequence[slength-1]);
for(i = slength-2; i >= 0; i--) printf(" %d", sequence[i]);
putchar('\n');
}
/* --- gray1_rr() ---
* Recursive sequence generation function.
*/
void gray2_rr(int n);
void gray1_rr(int n) {
if(n > 0) {
sequence[n-1] = 0;
gray1_rr(n-1);
sequence[n-1] = 1;
gray2_rr(n-1);
}
else {
seq_out();
}
}
/* --- gray2_rr() ---
* Recursive sequence generation function.
*/
void gray2_rr(int n) {
if(n > 0) {
sequence[n-1] = 1;
gray1_rr(n-1);
sequence[n-1] = 0;
gray2_rr(n-1);
}
else {
seq_out();
}
}
/* --- seq_i() ---
* Iterative sequence generation function.
*/
void gray_i(int n) {
int *up = malloc((n+1) * sizeof(int));
int i;
/* initialise sequence */
for(i = 0; i < n; i++) sequence[i] = 0;
/* algorithm */
for(i = 0; i < n+1; i++) up[i] = i+1;
do {
seq_out();
i = up[0];
sequence[i-1] = !sequence[i-1];
up[0] = 1;
up[i-1] = up[i];
up[i] = i+1;
} while(i < n+1);
}
/* --- gensequence() ---
* Generate sequence of specified length n.
*/
void gensequence(int n) {
sequence = malloc(n * sizeof(int));
slength = n;
#if GRAY_ALG == 0
gray1_rr(n);
#elif GRAY_ALG == 1
gray_i(n);
#endif
free(sequence);
}
/* --- main program --- */
int main(void) {
int n;
printf("Sequence length: ");
scanf("%d", &n);
gensequence(n);
return 0;
}
--
史役初，德步71師攻蘇軍穀倉。
三日後，守軍電：「嗚呼，缺糧也！請援之。」史達林覆電，云：「戰，可解饑也。」
復三日，守軍電：「嗚呼，無水也！請援之。」史對曰：「汝有彈藥，可以智取也！」
尋二日，守軍電：「嗚呼，彈藥已盡矣！」史答曰：「卿馬革裹屍，蘇聯不勝感激！」
守軍曰：「敢問高堂卡好！」此後不復回電求援。
——摘自《中華民國史記‧北狄列傳‧蘇聯》 ψ Prof. MRZ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.70.85.252