|
|||||||||||
| 技術(shù)交流 | 電路欣賞 | 工控天地 | 數(shù)字廣電 | 通信技術(shù) | 電源技術(shù) | 測控之家 | EMC技術(shù) | ARM技術(shù) | EDA技術(shù) | PCB技術(shù) | 嵌入式系統(tǒng) 驅(qū)動編程 | 集成電路 | 器件替換 | 模擬技術(shù) | 新手園地 | 單 片 機 | DSP技術(shù) | MCU技術(shù) | IC 設(shè)計 | IC 產(chǎn)業(yè) | CAN-bus/DeviceNe |
常用算法源代碼zt |
| 作者：劍寒情暖 欄目：單片機 |
循環(huán)冗余校驗 CRC的算法分析和程序?qū)崿F(xiàn) 西南交通大學計算機與通信工程學院 劉東 摘要 通信的目的是要把信息及時可靠地傳送給對方，因此要求一個通信系統(tǒng)傳輸消息必須可靠與快速，在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。為了解決可靠性，通信系統(tǒng)都采用了差錯控制。本文詳細介紹了循環(huán)冗余校驗CRC（Cyclic Redundancy Check）的差錯控制原理及其算法實現(xiàn)。 關(guān)鍵字 通信 循環(huán)冗余校驗 CRC-32 CRC-16 CRC-4 概述 在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。若要求快速，則必然使得每個數(shù)據(jù)碼元所占地時間縮短、波形變窄、能量減少，從而在受到干擾后產(chǎn)生錯誤地可能性增加，傳送信息地可靠性下降。若是要求可靠，則使得傳送消息地速率變慢。因此，如何合理地解決可靠性也速度這一對矛盾，是正確設(shè)計一個通信系統(tǒng)地關(guān)鍵問題之一。為保證傳輸過程的正確性，需要對通信過程進行差錯控制。差錯控制最常用的方法是自動請求重發(fā)方式（ARQ）、向前糾錯方式（FEC）和混合糾錯（HEC）。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸過程誤碼率較高時，采用FEC容易出現(xiàn)“亂糾”現(xiàn)象。HEC方式則式ARQ和FEC的結(jié)合。在許多數(shù)字通信中，廣泛采用ARQ方式，此時的差錯控制只需要檢錯功能。實現(xiàn)檢錯功能的差錯控制方法很多，傳統(tǒng)的有：奇偶校驗、校驗和檢測、重復碼校驗、恒比碼校驗、行列冗余碼校驗等，這些方法都是增加數(shù)據(jù)的冗余量，將校驗碼和數(shù)據(jù)一起發(fā)送到接受端。接受端對接受到的數(shù)據(jù)進行相同校驗，再將得到的校驗碼和接受到的校驗碼比較，如果二者一致則認為傳輸正確。但這些方法都有各自的缺點，誤判的概率比較高。 循環(huán)冗余校驗CRC（Cyclic Redundancy Check）是由分組線性碼的分支而來，其主要應用是二元碼組。編碼簡單且誤判概率很低，在通信系統(tǒng)中得到了廣泛的應用。下面重點介紹了CRC校驗的原理及其 算法實現(xiàn)。 一、循環(huán)冗余校驗碼（CRC） CRC校驗采用多項式編碼方法。被處理的數(shù)據(jù)塊可以看作是一個n階的二進制多項式，由 。如一個8位二進制數(shù)10110101可以表示為： 。多項式乘除法運算過程與普通代數(shù)多項式的乘除法相同。多項式的加減法運算以2為模，加減時不進，錯位，和邏輯異或運算一致。 采用CRC校驗時，發(fā)送方和接收方用同一個生成多項式g（x）,并且g（x）的首位和最后一位的系數(shù)必須為1。CRC的處理方法是：發(fā)送方以g（x）去除t（x），得到余數(shù)作為CRC校驗碼。校驗時，以計算的校正結(jié)果是否為0為據(jù)，判斷數(shù)據(jù)幀是否出錯。 CRC校驗可以100％地檢測出所有奇數(shù)個隨機錯誤和長度小于等于k（k為g（x）的階數(shù)）的突發(fā)錯誤。所以CRC的生成多項式的階數(shù)越高，那么誤判的概率就越小。CCITT建議：2048 kbit/s的PCM基群設(shè)備采用CRC-4方案，使用的CRC校驗碼生成多項式g（x）= 。采用16位CRC校驗，可以保證在 bit碼元中只含有一位未被檢測出的錯誤 。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗序列FCS中，使用CRC-16，其生成多項式g（x）= ；而在CCITT推薦的高級數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗序列FCS中，使用CCITT-16，其生成多項式g（x）= 。CRC-32的生成多項式g（x）= 。CRC-32出錯的概率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計算機等領(lǐng)域運用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內(nèi)，都采用了CRC校驗碼進行差錯控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進行差錯控制。 二、CRC校驗碼的算法分析 CRC校驗碼的編碼方法是用待發(fā)送的二進制數(shù)據(jù)t（x）除以生成多項式g（x），將最后的余數(shù)作為CRC校驗碼。其實現(xiàn)步驟如下： 設(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進制多項式t（x），生成多項式為r階的g（x）。在數(shù)據(jù)塊的末尾添加r個0，數(shù)據(jù)塊的長度增加到m+r位，對應的二進制多項式為 。 用生成多項式g（x）去除 ，求得余數(shù)為階數(shù)為r-1的二進制多項式y(tǒng)（x）。此二進制多項式y(tǒng)（x）就是t（x）經(jīng)過生成多項式g（x）編碼的CRC校驗碼。 用 以模2的方式減去y（x），得到二進制多項式 。 就是包含了CRC校驗碼的待發(fā)送字符串。 從CRC的編碼規(guī)則可以看出，CRC編碼實際上是將代發(fā)送的m位二進制多項式t（x）轉(zhuǎn)換成了可以被g（x）除盡的m+r位二進制多項式 ，所以解碼時可以用接受到的數(shù)據(jù)去除g（x），如果余數(shù)位零，則表示傳輸過程沒有錯誤；如果余數(shù)不為零，則在傳輸過程中肯定存在錯誤。許多CRC的硬件解碼電路就是按這種方式進行檢錯的。同時 可以看做是由t（x）和CRC校驗碼的組合，所以解碼時將接收到的二進制數(shù)據(jù)去掉尾部的r位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。 為了更清楚的了解CRC校驗碼的編碼過程，下面用一個簡單的例子來說明CRC校驗碼的編碼過程。由于CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一致，只有位數(shù)和生成多項式不一樣。為了敘述簡單，用一個CRC-4編碼的例子來說明CRC的編碼過程。 設(shè)待發(fā)送的數(shù)據(jù)t（x）為12位的二進制數(shù)據(jù)100100011100；CRC-4的生成多項式為g（x）= ，階數(shù)r為4，即10011。首先在t（x）的末尾添加4個0構(gòu)成 ，數(shù)據(jù)塊就成了1001000111000000。然后用g（x）去除 ，不用管商是多少，只需要求得余數(shù)y（x）。下表為給出了除法過程。 除數(shù)次數(shù) 被除數(shù)/ g（x）/結(jié)果 余數(shù) 0 1 001000111000000 100111000000 1 0011 0 000100111000000 1 1 00111000000 1000000 1 0011 0 00001000000 2 1 000000 1100 1 0011 0 001100 從上面表中可以看出，CRC編碼實際上是一個循環(huán)移位的模2運算。對CRC-4，我們假設(shè)有一個5 bits的寄存器，通過反復的移位和進行CRC的除法，那么最終該寄存器中的值去掉最高一位就是我們所要求的余數(shù)。所以可以將上述步驟用下面的流程描述： //reg是一個5 bits的寄存器 把reg中的值置0. 把原始的數(shù)據(jù)后添加r個0. While (數(shù)據(jù)未處理完) Begin If (reg首位是1) reg = reg XOR 0011. 把reg中的值左移一位，讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。 End reg的后四位就是我們所要求的余數(shù)。 這種算法簡單，容易實現(xiàn)，對任意長度生成多項式的G（x）都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用。但是如果發(fā)送的數(shù)據(jù)塊很長的話，這種方法就不太適合了。它一次只能處理一位數(shù)據(jù)，效率太低。為了提高處理效率，可以一次處理4位、8位、16位、32位。由于處理器的結(jié)構(gòu)基本上都支持8位數(shù)據(jù)的處理，所以一次處理8位比較合適。 為了對優(yōu)化后的算法有一種直觀的了解，先將上面的算法換個角度理解一下。在上面例子中，可以將編碼過程看作如下過程： 由于最后只需要余數(shù)，所以我們只看后四位。構(gòu)造一個四位的寄存器reg，初值為0，數(shù)據(jù)依次移入reg0（reg的0位），同時reg3的數(shù)據(jù)移出reg。有上面的算法可以知道，只有當移出的數(shù)據(jù)為1時，reg才和g（x）進行XOR運算；移出的數(shù)據(jù)為0時，reg不與g（x）進行XOR運算，相當與和0000進行XOR運算。就是說，reg和什么樣的數(shù)據(jù)進行XOR移出的數(shù)據(jù)決定。由于只有一個bit，所以有 種選擇。上述算法可以描述如下， //reg是一個4 bits的寄存器 初始化t[]={0011,0000} 把reg中的值置0. 把原始的數(shù)據(jù)后添加r個0. While (數(shù)據(jù)未處理完) Begin 把reg中的值左移一位，讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。 reg = reg XOR t[移出的位] End 上面算法是以bit為單位進行處理的，可以將上述算法擴展到8位，即以Byte為單位進行處理，即CRC-32。構(gòu)造一個四個Byte的寄存器reg，初值為0x00000000，數(shù)據(jù)依次移入reg0（reg的0字節(jié)，以下類似），同時reg3的數(shù)據(jù)移出reg。用上面的算法類推可知，移出的數(shù)據(jù)字節(jié)決定reg和什么樣的數(shù)據(jù)進行XOR。由于有8個bit，所以有 種選擇。上述算法可以描述如下： //reg是一個4 Byte的寄存器 初始化t[]＝{…}//共有 ＝256項 把reg中的值置0. 把原始的數(shù)據(jù)后添加r/8個0字節(jié). While (數(shù)據(jù)未處理完) Begin 把reg中的值左移一個字節(jié)，讀入一個新的字節(jié)并置于reg的第0個byte的位置。 reg = reg XOR t[移出的字節(jié)] End 算法的依據(jù)和多項式除法性質(zhì)有關(guān)。如果一個m位的多項式t（x）除以一個r階的生成多項式g（x）， ，將每一位 （0=<k<m）提出來，在后面不足r個0后，單獨去除g（x），得到的余式位 。則將 后得到的就是t（x）由生成多項式g（x）得到的余式。對于CRC-32，可以將每個字節(jié)在后面補上32個0后與生成多項式進行運算，得到余式和此字節(jié)唯一對應，這個余式就是上面算法種t[]中的值，由于一個字節(jié)有8位，所以t[]共有 ＝256項。多項式運算性質(zhì)可以參見參考文獻[1]。這種算法每次處理一個字節(jié)，通過查表法進行運算，大大提高了處理速度，故為大多數(shù)應用所采用。 三、CRC-32的程序?qū)崿F(xiàn)。 為了提高編碼效率，在實際運用中大多采用查表法來完成CRC-32校驗，下面是產(chǎn)生CRC-32校驗嗎的子程序。 unsigned LONG crc_32_tab[256]={ 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d };//事先計算出的參數(shù)表，共有256項，未全部列出。 unsigned LONG GenerateCRC32(CHAR xdata * DataBuf,unsigned LONG len) { unsigned LONG oldcrc32; unsigned LONG crc32; unsigned LONG oldcrc; unsigned int CHARcnt; CHAR c,t; oldcrc32 = 0x00000000; //初值為0 CHARcnt=0; while (len--) { |
| 2樓： | >>參與討論 |
| 作者： 劍寒情暖 于 2005/7/28 15:54:00 發(fā)布：
lzari的源代碼 一個對lzss編碼過的數(shù)據(jù)作自適應的0階arithmetic編碼的程序。比 lzh的壓縮率要高一點。 /************************************************************** LZARI.C -- A Data Compression Program (tab = 4 spaces) *************************************************************** 4/7/1989 Haruhiko Okumura Use, distribute, and modify this program freely. Please send me your improved versions. PC-VAN SCIENCE NIFTY-Serve PAF01022 CompuServe 74050,1022 **************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> /********** Bit I/O **********/ FILE *infile, *outfile; unsigned LONG int textsize = 0, codesize = 0, printcount = 0; void Error(CHAR *message) { printf("\n%s\n", message); exit(EXIT_FAILURE); } void PutBit(int bit) /* OUTPUT one bit (bit = 0,1) */ { static unsigned int buffer = 0, mask = 128; if (bit) buffer |= mask; if ((mask >>= 1) == 0) { if (putc(buffer, outfile) == EOF) Error("Write Error"); buffer = 0; mask = 128; codesize++; } } void FlushBitBuffer(void) /* Send remaining bits */ { int i; for (i = 0; i < 7; i++) PutBit(0); } int GetBit(void) /* Get one bit (0 or 1) */ { static unsigned int buffer, mask = 0; if ((mask >>= 1) == 0) { buffer = getc(infile); mask = 128; } return ((buffer & mask) != 0); } /********** LZSS with multiple binary trees **********/ #define N 4096 /* size of ring buffer */ #define F 60 /* upper limit for match_length */ #define THRESHOLD 2 /* encode string into position and length if match_length is greate r th n this */ #define NIL N /* index for root of binary search t rees */ unsigned CHAR text_buf[N + F - 1]; /* ring buffer of size N, with extra F-1 bytes to facilitate string comparison */ int match_position, match_length, /* of LONGest match. These a re set by the InsertNode() procedure. */ lson[N + 1], rson[N + 257], dad[N + 1]; /* left & right chi ldre & parents -- These constitute binary search trees. */ void InitTree(void) /* Initialize trees */ { int i; /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and left children of node i. These nodes need not be initialized. Also, dad[i] is the parent of node i. These are initialized to NIL (= N), which stands for 'not used.' For i = 0 to 255, rson[N + i + 1] is the root of the tree for strings that begin with CHARacter i. These are initialized to NIL. Note there are 256 trees. */ for (i = N + 1; i <= N + 256; i++) rson[i] = NIL; /* root */ for (i = 0; i < N; i++) dad[i] = NIL; /* node */ } void InsertNode(int r) /* Inserts string of length F, text_buf[r..r+F-1], into one of the trees (text_buf[r]'th tree) and returns the LONGest-match positio n and length via the GLOBAL variables match_position and match_length. If match_length = F, then removes the old node in favor of the ne w one, because the old one will be deleted sooner. Note r plays double role, as tree node and position in buffer. */ { int i, p, cmp, TEMP; unsigned CHAR *key; cmp = 1; key = &text_buf[r]; p = N + 1 + key[0]; rson[r] = lson[r] = NIL; match_length = 0; for ( ; ; ) { | |
| 3樓： | >>參與討論 |
| 作者： 劍寒情暖 于 2005/7/28 17:33:00 發(fā)布：
RC5算法 我最常用的分組算法之一，使用最大長度為256字節(jié)的變長密碼。 RC5接受兩個參數(shù)r：循環(huán)的次數(shù)，b：以word計算密碼長度。 初始化子密鑰數(shù)組S[2*r+2]： 定義P=0xb7e15163,Q=0x9e3779b9 S[0]=p,S[i]=(S[i+1]+Q) mod POWER(2,w); i=j=0;A=B=0; 循環(huán)3*max(2*r+2,b)次以下步驟： A=S[i]=rol((S[i]+A+B),3) B=K[j]=rol((K[j]+A+B),(A+B)); i=(i+1) mod 2*r+2 j=(j+1) mod b 加密算法： 對長度為2words的明文M[2]作以下變換，得到密文C[2] C[0]=M[0]+S[0];C[1]=M[1]+S[1]; For i=1 to r C[0]=rol((C[0] xor C[1]),C[1])+S[2*i] C[1]=rol((C[1] XOR C[0]),M[0])+S[2*i+1] 解密算法： 對長度為2words的密文C[2]作以下變換，得到明文M[2] For i=r downto 1 C[1]=ror((C[1]-S[2*i+1],C[0]) xor C[0] C[0]=ror((C[0]-S[2*i],C[1]) xor C[1] EndFor M[1]=C[1]-S[1] M[0]=C[0]-S[0] |
|
| 4樓： | >>參與討論 |
| 作者： 劍寒情暖 于 2005/7/28 17:34:00 發(fā)布：
Win95 PWL文件password加密算法 最近研究了一下Win95/WFWG3.11之PWL文件，因為前面曾有一個glide.c程序能解出PWL文件的一些資源，但卻無法給出Password. 用SoftICE跟了幾回，發(fā)現(xiàn)涉及password的代碼均在MSPWL32.DLL中，以下的程序為將其匯編碼翻譯成C所成。 盡管加密算法研究出來了，但破解方法卻不大好弄(我覺得一個好的加密算法應該 是沒有比窮舉法更優(yōu)的解密方法的，若哪位大蝦有好的破解方法，不妨POST上來共同 討論) 但此password得到方法好象只有技術(shù)意義，畢竟解出來泥并不能得到root權(quán)限， 而只是別人的Preference Settings! :-( 關(guān)于PWL文件的一些說明：14個字符長的密碼(均轉(zhuǎn)為大寫)，用它生成一個32位的 密鑰，由以下算法求得一個XOR串，接下來用此XOR串 XOR 20 bytes長的UserName(也 轉(zhuǎn)為大寫), 結(jié)果存于PWL文件offset 0x208-0x21B, 0x21C開始為一系列指 向鬃試串的 指針(當然已XOR過了)。資源串中保存的主要是該USER的一些Shared Directory的口令， 資源串也分別與XOR串 XOR, PWL文件. // ================= CRYPT.CPP 1997.8.16 ================ #include <stdio.h> #include <ctype.h> #include <string.h> /* The WFWG3.11/Win95's PWL file crypt algorithm demonstration: codes extracted from \Win95\SYSTEM\MSPWL32.DLL You may use SoftICE to trace it or W32DASM to disassemble it, the offset address of each routine is listed below(You may find the corresponding codes in W32DASM's ALF file according to the offset VALUE) */ typedef unsigned CHAR BYTE; inline void SwapByte(BYTE& c1,BYTE& c2) { BYTE TEMP; TEMP = c1; c1 = c2; c2 = TEMP; } // generate a 32 bit key according to the password(capital) // translate from MSPWL32.DLL's codes beginning at 7FCB1972h unsigned LONG GenerateKey(CHAR *pw) { int i, len; unsigned LONG sum = 0; len = strlen(pw); for(i = 0; i <= len; i++) { sum += toupper(pw[i]); sum = (sum << 0x7) | (sum >> 0x19); // same as rol sum,7 } return sum; } // translate from MSPWL32.DLL's codes beginning at 7FCB1000h void GenerateStream(BYTE *stream,unsigned LONG key) { BYTE keyCHAR[4]; int i,j,shift=0; BYTE index=0; *((unsigned LONG*)keyCHAR) = key; for(i = 0; i < 256; i++) stream[i] = (BYTE)i; for(i = 0; i < 256; i++) { index += keyCHAR[shift] + stream[i]; SwapByte(stream[i],stream[index]); shift = (shift+1) % 4; } } // translate from MSPWL32.DLL's codes beginning at 7FCB1088h void GenerateXorString(BYTE *src,BYTE *dest) { BYTE j=0,index; int i; for(i = 1; i <= 255; i++) { j += src[i]; SwapByte(src[i],src[j]); index = src[i] + src[j]; dest[i-1] = src[index]; } } int main(int argc,CHAR *argv[]) { unsigned LONG key; BYTE table[256]; BYTE xorstr[256]; int i,len; if (argc < 3) { printf("Usage: Crypt username password\n"); printf("Author: Raner,DCS,Tsinghua Univ\n"); printf("Comment: This program is used to demonstrate the Win95 PWL file crypt\n"); printf(" method. You may compare the crypted username string with the\n"); printf(" string beginning at offset 0x208 of PWL file. \n"); return 1; } key = GenerateKey(argv[2]); printf("\n32 Bits Key:\n 0x%08lX\n",key); GenerateStream(table,key); GenerateXorString(table,xorstr); printf("\nXor String:"); for(i = 0; i < 54; i++) { if ( i % 16 == 0) printf("\n "); printf("%02X,",xorstr[i]); } printf("......\n"); len = strlen(argv[1]); for(i = 0; i < len; i++) xorstr[i] ^= (BYTE)toupper(argv[1][i]); printf("\nCrypted UserName:\n "); for(i = 0; i < 20; i++) printf("%02X%c",xorstr[i], i == 19 ? '\n' : ','); /* You may debug username.pwl & d 308 to verify its correctness. Crypted username(20 bytes) is saved at offset 0x208 of *.pwl */ return 0; } |
|
| 5樓： | >>參與討論 |
| 作者： 劍寒情暖 于 2005/7/28 17:35:00 發(fā)布：
黑白棋子 //黑白棋子 #include <iostream.h> int sp; CHAR c[20]; int i,m; void mv(int); void mos(int); void main() { int n; cout<<"Input (n>=4)";cin>>n; m=n; for(i=1;i<=n;i++) {c[i]='0';c[i+n]='1';} sp=n*2+1; mv(n); cin>>i; } void mv(int n) { if(n==4) { mos(4); mos(8); mos(2); mos(7); mos(1); } else { mos(n); mos(2*n-1); mv(n-1); } } void mos(int k) { c[sp]=c[k]; c[sp+1]=c[k+1]; sp=k; c[k]='_'; c[k+1]='_'; for(i=1;i<=2*m+2;i++) cout<<c[i]; cout<<endl; } |
|
| 6樓： | >>參與討論 |
| 作者： 劍寒情暖 于 2005/7/28 17:36:00 發(fā)布：
24, 看大家一直在孜孜以求的計算24, 不如貼個程序出來, 可以在1秒種之內(nèi)解決任何計算24的問題. 當然想算25, 26... 也是可以的. 希望以此作為24問題的終結(jié). #include "stdafx.h" // //原理, 將4個數(shù)字和3個運算符按"波蘭表達式"組成一個序列, // 計算該序列的值是否為所求目標. 可以對這個序列的組成 // 進行遍歷, 以確定是否有解. //根據(jù)我的計算如果只限于用1-10之間的數(shù)字計算24, 總共有 // 715個不同的題目, 其中566個有解. 如果是1-13, 則有 // 1820個不同的題目, 其中1362個有解 // int total = 0; //解的個數(shù) int sp; //當前表達式棧指針 int s[7]; //表達式棧 void Evaluate(int& fz, int& fm) //計算表達式的值, fz, fm為計算結(jié)果的分子, 分母 { int op, l, m, opn[4]; op = s[sp]; //取棧頂元素 for (l = 0; l < 4; l += 2) { if ((m = s[++sp]) > 0) //是數(shù)字 { opn[l] = m; opn[l + 1] = 1; } else //是運算符 Evaluate(opn[l], opn[l + 1]); } //根據(jù)運算符進行計算 //opn[0]/opn[1] 是第一個操作數(shù), //opn[2]/opn[3] 是第二個操作數(shù), SWITCH (op) { case -4: //乘法 fz = opn[0] * opn[2]; fm = opn[1] * opn[3]; break; case -3: //加法 fz = opn[0] * opn[3] + opn[1] * opn[2]; fm = opn[1] * opn[3]; break; case -2: //減法 fz = opn[0] * opn[3] - opn[1] * opn[2]; fm = opn[1] * opn[3]; break; case -1: //除法 fz = opn[0] * opn[3]; fm = opn[1] * opn[2]; break; } } void DISPLAY(CString& m) //將表達式轉(zhuǎn)換為字符串 { int i; CString n; CString n; m = ""; for (i = 0; i < 7; i++) { SWITCH (s[i]) { case -4: m += " *"; break; case -3: m += " +"; break; case -2: m += " -"; break; case -1: m += " /"; break; default: n.Format("%3d", s[i]); m += n; break; } } } void Compute(int target, int a, int b, int c, int d, CStringArray& ma) // target - 計算結(jié)果(一般為24) // a, b, c, d - 參加計算的4個數(shù) // ma - 解的字符串表達形式 { int l1, l2, l3, op1, op2, op3; int l, fz, fm, num[4]; CString m; //記錄表達式中間四個元素的排列方式 // 其中l(wèi)oc[i][0], loc[i][1]表示第二, 第三兩個運算符的位置 // loc[i][2], loc[i][3]表示第一, 第二兩個操作數(shù)的位置 int loc[5][4] = {{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3}, {2, 3, 1, 4}, {2, 4, 1, 3}}; //num中記錄a, b, c, d的一個排列 for (l1 = 0; l1 < 4; l1++) { num[l1] = a; for (l2 = 0; l2 < 4; l2++) { if (l2 == l1) continue; num[l2] = b; for (l3 = 0; l3 < 4; l3++) { if (l3 == l1 || l3 == l2) continue; num[l3] = c; num[6 - l1 - l2 - l3] = d; //表達式最后兩個必須是數(shù)字 s[5] = num[2]; s[6] = num[3]; for (l = 0; l < 5; l++) { s[loc[l][2]] = num[0]; s[loc[l][3]] = num[1]; for (op1 = -4; op1 < 0; op1++) { //表達式第一個必須運算符 s[0] = op1; for (op2 = -4; op2 < 0; op2++) { s[loc[l][0]] = op2; for (op3 = -4; op3 < 0; op3++) { s[loc[l][1]] = op3; sp = 0; Evaluate(fz, fm); //分母不為0, 可以整除, 商為24表示計算成功 if (fm != 0 && fz % fm == 0 && fz / fm == target) { DISPLAY(m); ma.Add(m); total++; //這里加return就是只求一個解, //否則是求出全部解(沒有考慮剔除重復解) return; } } } } } } } } } |
|
| 7樓： | >>參與討論 |
| 作者： 劍寒情暖 于 2005/7/28 17:37:00 發(fā)布：
Huffman算法 以前寫的一個C程序不見了,剛好在華工的站上 有VC的,就順手貼了過來了,算法流程應該是最 重要的,很多講數(shù)字壓縮的都有Huffman算法. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <dir.h> #include <dos.h> #include <direct.h> #include <bios.h> #include <conio.h> #include <time.h> #define EXIT_OK 0 #define EXIT_FAILED -1 ////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// FILE *infile, *outfile; unsigned LONG int textsize = 0, codesize = 0, printcount = 0; void Error(CHAR *message) { printf("\n%s\n", message); exit(-1); } /* LZSS Parameters */ #define N 4096 /* Size of string buffer */ #define F 60 //* Size of look-ahead buffer 60 #define THRESHOLD 2 #define NIL N /* End of tree's node */ unsigned CHAR text_buf[N + F -1];//-1 int match_position, match_length, lson[N + 1], rson[N + 257], dad[N + 1]; void InitTree(void) /* Initializing tree */ { int i; for (i = N + 1; i <= N + 256; i++) rson[i] = NIL; /* root */ for (i = 0; i < N; i++) dad[i] = NIL; /* node */ } void InsertNode(int r) /* Inserting node to the tree */ { int i, p, cmp; unsigned CHAR *key; unsigned c; cmp = 1; key = &text_buf[r]; p = N + 1 + key[0]; rson[r] = lson[r] = NIL; match_length = 0; for ( ; ; ) { if (cmp >= 0) { if (rson[p] != NIL) p = rson[p]; else { rson[p] = r; dad[r] = p; return; } } else { if (lson[p] != NIL) p = lson[p]; else { lson[p] = r; dad[r] = p; return; } } for (i = 1; i < F; i++) if ((cmp = key[i] - text_buf[p + i]) != 0) break; if (i > THRESHOLD) { if (i > match_length) { match_position = ((r - p) & (N - 1)) - 1; if ((match_length = i) >= F) break; |
|
| 8樓： | >>參與討論 |
| 作者： 劍寒情暖 于 2005/7/28 17:38:00 發(fā)布：
最小生成樹 最小生成樹是數(shù)據(jù)結(jié)構(gòu)中圖的一種重要應用,它的要求是從一個帶權(quán)無向完全圖 中選擇n－1條邊并使這個圖仍然連通(也即得到了一棵生成樹),同時還要考慮使樹 的權(quán)最小。 為了得到最小生成樹,人們設(shè)計了很多算法,最著名的有prim算法和kruskal算 法。教材中介紹了prim算法,但是講得不夠詳細,理解起來比較困難,為了幫助大家 更好的理解這一算法,本文對書中的內(nèi)容作了進一步的細化,希望能對大家有所幫助 。 假設(shè)V是圖中頂點的集合,E是圖中邊的集合,TE為最小生成樹中的邊的集合,則 prim算法通過以下步驟可以得到最小生成樹: 1:初始化:U={u 0},TE={}。此步驟設(shè)立一個只有結(jié)點u 0的結(jié)點集U和一個空 的邊集TE作為最小生成樹的初始行態(tài),在隨后的算法執(zhí)行中,這個行態(tài)會不斷的發(fā)生 變化,直到得到最小生成樹為止。 2:在所有u∈U,v∈V－U的邊(u,v)∈E中,找一條權(quán)最小的邊(u 0,v 0)，將此邊 加進集合TE中，并將此邊的非U中頂點加入U中。此步驟的功能是在邊集E中找一條 邊,要求這條邊滿足以下條件:首先邊的兩個頂點要分別在頂點集合U和V－U中,其次 邊的權(quán)要最小。找到這條邊以后,把這條邊放到邊集TE中,并把這條邊上不在U中的 那個頂點加入到U中。這一步驟在算法中應執(zhí)行多次,每執(zhí)行一次,集合TE和U都將發(fā) 生變化,分別增加一條邊和一個頂點,因此,TE和U是兩個動態(tài)的集合,這一點在理解 算法時要密切注意。 3:如果U=V,則算法結(jié)束;否則重復步驟2�？梢园驯静襟E看成循環(huán)終止條件。我 們可以算出當U=V時,步驟2共執(zhí)行了n－1次(設(shè)n為圖中頂點的數(shù)目),TE中也增加了 n－1條邊,這n－1條邊就是需要求出的最小生成樹的邊。 了解了prim算法的基本思想以后,下面我們就可以看看具體的算法。 為了和教材保持一致,我們?nèi)匀灰?guī)定:連通網(wǎng)用鄰接矩陣net表示,若兩個頂點之 間不存在邊,其權(quán)值為計算機內(nèi)允許最大值,否則為對應邊上的權(quán)值。 首先定義數(shù)據(jù)類型: type adjmatrix=array [1．.n,1..n] of real; //定義一個n＊n的矩陣類型adjmatrix,以便存儲鄰接矩陣// edge=record beg,en:1..n; length:real; end; //定義邊的存儲結(jié)構(gòu)為edge,其中beg是邊的起點, en 是邊的終點,length是邊 的權(quán)值// treetype=array [1..n－1] of edge; //定義一個基類型為edge的數(shù)組類型 treetype,其元素個數(shù)為n－1個// var net:adjmatrix; //定義一個adjmatrix類型的變量net,圖的鄰接矩陣就存放在net中// tree:treetype; //定義一個treetype類型的變量tree,tree中可以存放n－1條邊的信息，包括 起點、終點及權(quán)值。在算法結(jié)束后，最小生成樹的n－1 條邊就存放在tree中// 算法如下(設(shè)n為構(gòu)造的出發(fā)點)： procedure prim(net:adjmatrix;var tree:treetype); //過程首部.參數(shù)的含義是:值參數(shù)net傳遞圖的鄰接矩陣,變參tree指明最小生 成樹的存放地址// begin for v:=1 to n－1 do //此循環(huán)將頂點n與圖中其它n－1個頂點形成的n－1條邊存放在變量tree中 // [tree[v].beg:=n; tree[v].en:=v; tree[v].length:=net[v]] for k:=1 to n－1 do //此循環(huán)執(zhí)行算法思想中的步驟2,循環(huán)體每執(zhí)行一次,TE中將增加一條邊,在算 法中,這條增加的邊存放在變量tree中的第k個元素上,可以這樣認為,tree中從第1 到第k號元素中存放了TE和U的信息。注意:在算法思想中我們特別提醒了TE和U的動 態(tài)性,表現(xiàn)在算法中,這種動態(tài)性 體現(xiàn)在循環(huán)變量k的變化上。// [min:=tree][k].length; for j:=k to n－1 do if tree[j].length<min then [min:=tree][j].length; m:=j;] //上面兩條語句用于搜索權(quán)值最小的邊// v:=tree[m].en; //此語句記錄剛加入TE中的邊的終點,也即即將加入U中的頂點// edge:=tree[m]; tree[m]:=tree[k]; tree[k]:=edge; //上面三句用于將剛找到的邊存儲到變量tree的第k號元素上// for j:=k＋1 to n－1 do //此循環(huán)用于更新tree中第k＋1到第n－1號元素。更新以后這些元素中的en子 項是各不相同的,它們的全部就是集合V－U;beg子項則可以相同,但它們需滿足兩個 條件:一是應屬于集合U;另一是beg子項和en子項行成的邊,在所有與頂點en聯(lián)系的 邊中權(quán)值應最小。// [d:=net][v.tree[j].en]; if d<tree[j].length then [tree[j].length:=d; tree[j].beg:=v;] ] ] for j:=1 to n－1 do //此循環(huán)用于輸出最小生成樹// writeln(tree[j].beg,tree[j].en,tree[j].length); end; 此算法的精妙之處在于對求權(quán)值最小的邊這一問題的分解(也正是由于這種分 解，而導致了算法理解上的困難)。按照常規(guī)的思路,這一問題應該這樣解決:分別 從集合V－U和U中取一頂點,從鄰接矩陣中找到這兩個頂點行成的邊的權(quán)值,設(shè)V－U 中有m個頂點,U中有n個頂點,則需要找到m＊n個權(quán)值,在這m＊n個權(quán)值中,再查找權(quán) 最小的邊。循環(huán)每執(zhí)行一次,這一過程都應重復一次，相對來說計算量比較大。而 本算法則利用了變量tree中第k＋1到第n－1號元素來存放到上一循環(huán)為止的一些比 較結(jié)果,如以第k＋1號元素為例,其存放的是集合U中某一頂點到頂點tree.en的邊, 這條邊是到該點的所有邊中權(quán)值最小的邊,所以,求權(quán)最小的邊這一問題,通過比較 第k＋1號到第n－1號元素的權(quán)的大小就可以解決,每次循環(huán)只用比較n－k－2次即可 ，從而大大減小了計算量。 |
|
| 9樓： | >>參與討論 |
| 作者： liaozhihua 于 2005/7/28 17:55:00 發(fā)布：
最好打個包。。。 |
|
| 10樓： | >>參與討論 |
| 作者： 雷風 于 2005/7/28 18:42:00 發(fā)布：
同意 |
|
| 11樓： | >>參與討論 |
| 作者： yanfengzhu 于 2005/7/28 19:18:00 發(fā)布：
收藏 |
|
| 12樓： | >>參與討論 |
| 作者： tanjinhui 于 2005/7/28 21:23:00 發(fā)布：
收下!! |
|
|
|
| 免費注冊為維庫電子開發(fā)網(wǎng)會員，參與電子工程師社區(qū)討論，點此進入 |
Copyright © 1998-2006 m.58mhw.cn 浙ICP證030469號 |