c语言常用经典算法分析

http://www.lisdn.com

c 语言常用经典算法分析
linux 软件开发

1.冒泡法：

#include <iostream.h>

void BubbleSort(int* pData,int Count)

{

int iTemp;

for(int i=1;i<Count;i )

{

for(int j=Count-1;j>=i;j--)

{

http://www.lisdn.com

http://www.lisdn.com

if(pData[j]<pData[j-1])

{

iTemp = pData[j-1];

pData[j-1] = pData[j];

pData[j] = iTemp;

}

}

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

http://www.lisdn.com

http://www.lisdn.com

BubbleSort(data,7);

for (int i=0;i<7;i )

cout<<data[i]<<" ";

cout<<"\n";

}

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

2.交换法：

#include <iostream.h>

http://www.lisdn.com

http://www.lisdn.com

void ExchangeSort(int* pData,int Count)

{

int iTemp;

for(int i=0;i<Count-1;i )

{

for(int j=i 1;j<Count;j )

{

if(pData[j]<pData[i])

{

iTemp = pData[i];

pData[i] = pData[j];

pData[j] = iTemp;

http://www.lisdn.com

http://www.lisdn.com

}

}

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

ExchangeSort(data,7);

for (int i=0;i<7;i )

cout<<data[i]<<" ";

cout<<"\n";

}

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

3.选择法：

http://www.lisdn.com

http://www.lisdn.com

#include <iostream.h>

void SelectSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=0;i<Count-1;i )

{

iTemp = pData[i];

iPos = i;

for(int j=i 1;j<Count;j )

{

if(pData[j]<iTemp)

http://www.lisdn.com

http://www.lisdn.com

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData[i];

pData[i] = iTemp;

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

http://www.lisdn.com

http://www.lisdn.com

SelectSort(data,7);

for (int i=0;i<7;i )

cout<<data[i]<<" ";

cout<<"\n";

}

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

4.插入法：

#include <iostream.h>

void InsertSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=1;i<Count;i )

{

http://www.lisdn.com

http://www.lisdn.com

iTemp = pData[i];

iPos = i-1;

while((iPos>=0) && (iTemp<pData[iPos]))

{

pData[iPos 1] = pData[iPos];

iPos--;

}

pData[iPos 1] = iTemp;

}

}

http://www.lisdn.com

http://www.lisdn.com

void main()

{

int data[] = {10,9,8,7,6,5,4};

InsertSort(data,7);

for (int i=0;i<7;i )

cout<<data[i]<<" ";

cout<<"\n";

}

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

#include <iostream>

http://www.lisdn.com

http://www.lisdn.com

using namespace std;

void coutstream(int a[],int n){

for(int i=0;i!=n;i )

cout<<a[i]<<" ";

}

void insertsort(int a[],int n){

int temp;

for(int i=1;i<n;i )

{

int j=i;

temp=a[i]; //先把 a[i]位置的数据存起来

http://www.lisdn.com

http://www.lisdn.com

while(j>0&&temp<a[j-1])

{

a[j]=a[j-1];

j--;

}

a[j]=temp;

}

}

int main()

{

http://www.lisdn.com

http://www.lisdn.com

int a[5]={1,6,4,8,4};

insertsort(a,5);//插入排序

coutstream(a,5);//

return 0;

}

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.lisdn.com

http://www.lisdn.com

http://www.CodeHighlighter.com/

1.快速排序：

#include <iostream.h>

void run(int* pData,int left,int right)

{

int i,j;

int middle,iTemp;

http://www.lisdn.com

http://www.lisdn.com

i = left;

j = right;

middle = pData[(left right)/2]; //求中间值

do{

while((pData[i]<middle) && (i<right))//从左扫描大于中值的数

i ;

while((pData[j]>middle) && (j>left))//从右扫描大于中值的数

j--;

if(i<=j)//找到了一对值

{

//交换

iTemp = pData[i];

http://www.lisdn.com

http://www.lisdn.com

pData[i] = pData[j];

pData[j] = iTemp;

i ;

j--;

}

}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）

//当左边部分有值(left<j)，递归左半边

if(left<j)

run(pData,left,j);

//当右边部分有值(right>i)，递归右半边

if(right>i)

run(pData,i,right);

http://www.lisdn.com

http://www.lisdn.com

}

void QuickSort(int* pData,int Count)

{

run(pData,0,Count-1);

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

QuickSort(data,7);

for (int i=0;i<7;i )

http://www.lisdn.com

http://www.lisdn.com

cout<<data[i]<<" ";

cout<<"\n";

}

1.数组的大小是 2 的幂，这样分下去始终可以被 2 整除。假设为 2 的 k 次方，即 k=log2(n)。

2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

1.双向冒泡：

http://www.lisdn.com

http://www.lisdn.com

#include <iostream.h>

void Bubble2Sort(int* pData,int Count)

{

int iTemp;

int left = 1;

int right =Count -1;

int t;

do

{

//正向的部分

for(int i=right;i>=left;i--)

http://www.lisdn.com

http://www.lisdn.com

{

if(pData[i]<pData[i-1])

{

iTemp = pData[i];

pData[i] = pData[i-1];

pData[i-1] = iTemp;

t = i;

}

}

left = t 1;

//反向的部分

for(i=left;i<right 1;i )

http://www.lisdn.com

http://www.lisdn.com

{

if(pData[i]<pData[i-1])

{

iTemp = pData[i];

pData[i] = pData[i-1];

pData[i-1] = iTemp;

t = i;

}

}

right = t-1;

}while(left<=right);

}

http://www.lisdn.com

http://www.lisdn.com

void main()

{

int data[] = {10,9,8,7,6,5,4};

Bubble2Sort(data,7);

for (int i=0;i<7;i )

cout<<data[i]<<" ";

cout<<"\n";

}

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

#include <iostream>

using namespace std;

class QuickSort

{

public:

void quick_sort(int* x,int low,int high)

{

http://www.lisdn.com

http://www.lisdn.com

int pivotkey;

if(low <high)

{

pivotkey=partion(x,low,high);

quick_sort(x,low,pivotkey-1);

quick_sort(x,pivotkey 1,high);

}

}

int partion(int* x,int low,int high)

{

int pivotkey;

pivotkey=x[low];

while(low <high)

http://www.lisdn.com

http://www.lisdn.com

{

while (low <high&&x[high]>=pivotkey)

--high; //还有 while 循环只执行这一句

x[low]=x[high];

while (low <high&&x[low] <=pivotkey)

low; //还有 while 循环只执行这一句

x[high]=x[low];

}

x[low]=pivotkey;

return low;

}

};

http://www.lisdn.com

http://www.lisdn.com

int main()

{

int x[10]={52,49,80,36,14,58,61,97,23,65};

QuickSort qs;

qs.quick_sort(x,0,9);

cout <<"排好序的数字序列为：" <<endl;

for (int i=0;i <10;i )

{

printf("%d ",x[i]);

}

return 0;

}

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

2.SHELL 排序

#include <iostream.h>

http://www.lisdn.com

http://www.lisdn.com

void ShellSort(int* pData,int Count)

{

int step[4];

step[0] = 9;

step[1] = 5;

step[2] = 3;

step[3] = 1;

int iTemp;

int k,s,w;

for(int i=0;i<4;i )

{

k = step[i];

http://www.lisdn.com

http://www.lisdn.com

s = -k;

for(int j=k;j<Count;j )

{

iTemp = pData[j];

w = j-k;//求上 step 个元素的下标

if(s ==0)

{

s = -k;

s ;

pData[s] = iTemp;

}

while((iTemp<pData[w]) && (w>=0) && (w<=Count))

http://www.lisdn.com

http://www.lisdn.com

{

pData[w k] = pData[w];

w = w-k;

}

pData[w k] = iTemp;

}

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};

ShellSort(data,12);

http://www.lisdn.com

http://www.lisdn.com

for (int i=0;i<12;i )

cout<<data[i]<<" ";

cout<<"\n";

}

C/C code

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

#include <iostream>

using namespace std;

void maopao(int *list,int n)

{

int i=n,j,temp;

bool exchange;//当数据已经排好时，退出循环

for(i=0;i<n;i )

http://www.lisdn.com

http://www.lisdn.com

{

exchange=false;

for (j=0;j<n-i-1;j )

{

if (list[j]>list[j 1])

{

temp=list[j];

list[j]=list[j 1];

list[j 1]=temp;

exchange=true;

}

http://www.lisdn.com

http://www.lisdn.com

}

if (!exchange)

{

return;

}

}

}

int main()

{

int a[7]={32,43,22,52,2,10,30};

maopao(a,7);

for(int i=0;i<7;i )

cout<<a[i]<<" ";

http://www.lisdn.com

http://www.lisdn.com

return 0;

}

http://www.lisdn.com

http://www.lisdn.com

shell 排序的思想是根据步长由长到短分组，进行排序，直到步长为 1 为止，属于插入排序 的一种。下面用个例子更好的理解一下

1.首先设定 gap=n/2=4 于是分组 32，34 排序 32，34 43， 8 8， 43 56，54 54，56 99，76 76，99 数列变成 32，8，54，76，34，43，56，99

2.gap=gap/2=2 于是分组 32，54，34，56 排序 32，34，54，56 8，76，43，99 8，43，76，99 于是数列变成 32，8，34，43，54，76，56，99

3.gap=gap/2=1 于是分组 32，8，34，43，54，76，56，99 排序 8，32，34，43，54，56，76，99 gap=1 结束……

http://www.lisdn.com

http://www.lisdn.com

void shellsort(int v[], int n) { int gap, i, j, temp; for(gap=n/2;gap>0;gap/=2) //设定步长 for(i=gap;i <n; i) //在元素间移动为止 for(j=i-gap; j>=0&&v[j]>v[j gap]; j-=gap){ //比较相距 gap 的元素，逆序互换 temp=v[j]; v[j]=v[j gap]; v[j gap]=temp; } }

http://blog.csdn.net/mifeixq/archive/2008/09/18/2946405.aspx 网友回复:帮顶 网友回复: C/C code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.lisdn.com

http://www.lisdn.com

http://www.CodeHighlighter.com/

//帕斯卡恒等式为 C(n,k)=C(n-1,k-1) C(n-1,k)

long fun(long n,long r)

{

if(r<0||n<0)

{

printf("\nError.Exit!");

exit(1);

}

http://www.lisdn.com

http://www.lisdn.com

if(r>n) return 0;

if(r==1||r==n-1)//根据组合定义，我们有 C(n,1)=C(n,n-1)=n

return n;

if(r==0||r==n)//根据组合定义，我们有 C(n,0)=C(n,n)=1

return 1;

return fun(n-1,r) fun(n-1,r-1);//帕斯卡组合公式

}

//选择法对数组排序的函数模板

template <class T>

void selectsort(T arr[],int size)

{

T temp;

http://www.lisdn.com

http://www.lisdn.com

int i,j;

for (i=0;i<size-1;i )

for (j=i 1;j<size;j )

if (arr[i]>arr[j])

{

temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

}

//冒泡法对数组排序的函数模板

http://www.lisdn.com

http://www.lisdn.com

template<class T>

void bubblesort(T *d,int n)

{

int i,j;

T t;

for(i=0;i<n-1;i )

for(j=0;j<n-i-1;j )

if(d[j]>d[j 1])

{

t=d[j];

d[j]=d[j 1];

d[j 1]=t;

}

http://www.lisdn.com

http://www.lisdn.com

}

//插入法对数组排序的函数模板

template <class T>

void InsertSort(T A[], int n)

{

int i, j;

T

temp;

for (i = 1; i < n; i )

{

temp = A[i];

for (j=i-1; j>=0&&temp<A[j];j--)

http://www.lisdn.com

http://www.lisdn.com

A[j 1]=A[j];

A[j 1] = temp;

}

}

//二分查找法的函数模板

template <class T>

int binary_search(T array[], T value, int size)

{

int high = size-1, low = 0, mid;

while (low<=high)

{

mid = (high

low) / 2;

http://www.lisdn.com

http://www.lisdn.com

if (value < array[mid])

high = mid - 1;

else if(value>array[mid])

low = mid

1;

else return mid;

}

return -1;

}

//将 2~36 进制数转换成 10 进制数

http://www.lisdn.com

http://www.lisdn.com

unsigned int OthToDec(char *oth, int base) //base 为已知数的进制

{

unsigned int i=0, dec=0;

while (oth[i])

{

dec*=base;

if (oth[i]>='0' && oth[i]<='9')

dec =oth[i]&15;//dec =oth[i]-48;

else if (oth[i]>='A' && oth[i]<='Z')

dec =oth[i]-55;

else if (oth[i]>='a' && oth[i]<='z')

dec =oth[i]-87;

i ;

http://www.lisdn.com

http://www.lisdn.com

}

return dec;

}

//将 10 进制(无符号)转 2~36 进制数

char *DecToOth(char *oth, unsigned int dec, int base)

//base 为要转换的数的进制

{

char ch, *left=oth, *right=oth,num[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

do

{

*right=num[dec 簊 e];

right ;

http://www.lisdn.com

http://www.lisdn.com

}while (dec/=base);

*right='\0';

right--;

while (left<right)

{

ch=*left;

*left=*right;

*right=ch;

left ;right--;

}

return oth;

}

http://www.lisdn.com

http://www.lisdn.com

//统计 substr 在 str 中的个数

int fun(char *str,char *substr)

{

int n=0;

char *q;

q=substr;

while(*str!='\0')

{

if(*str==*substr)

{

str ;

substr ;

http://www.lisdn.com

http://www.lisdn.com

if(*substr=='\0')

{

n ;

substr=q;

}

}

else

{

str ;substr=q;

}

}

return n;

}

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

#include <stdio.h>

#include <stdlib.h>

main()

{

http://www.lisdn.com

http://www.lisdn.com

int m,n,i=1,j,k=1,per,o;

printf("请输入总共的人数,记为 n \n");

scanf("%d",&n);

int array[n 1];

int order[n 1];

printf("请输入几号出圈,记为 m \n");

scanf("%d",&m);

printf("\n**************************************\n");

for(;i <n;i )//数组链表模拟

array[i]=i 1;

array[n]=1;

http://www.lisdn.com

http://www.lisdn.com

printf("%d ",array[n]);

i=1;j=1;per=n;

while(array[i]!=i){

if(k==m){

order[j]=i;

j ;

array[per]=array[i];

k=0;

for(o=1;o <=j;o )

printf("%d* ",order[o]);

}

else{printf("%d ",array[i]);

http://www.lisdn.com

http://www.lisdn.com

per=i;

i=array[i];

k ;

}

}

order[n]=i;

printf("\n**************************************\n");

for(i=1;i <=n;i )

printf("%d ",order[i]);

system("pause");

http://www.lisdn.com

http://www.lisdn.com

return 0;

}

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h>

#define N 4096 /* size of ring buffer */

#define F 18 /* upper limit for match_length */

#define THRESHOLD 2 /* encode string into position and length

if match_length is greater than this */

#define NIL N /* index for root of binary search trees */

unsigned long int

textsize = 0, /* text size counter */

codesize = 0, /* code size counter */

printcount = 0; /* counter for reporting progress every 1K bytes */

unsigned char

http://www.lisdn.com

http://www.lisdn.com

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 are

set by the InsertNode() procedure. */

lson[N 1], rson[N 257], dad[N 1]; /* left & right children &

parents -- These constitute binary search trees. */

FILE *infile, *outfile; /* input & output files */

void InitTree(void) /* initialize trees */

{

int i;

http://www.lisdn.com

http://www.lisdn.com

/* 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;

for (i = 0; i < N; i ) dad[i] = NIL;

}

void InsertNode(int r)

/* Inserts string of length F, text_buf[r..r F-1], into one of the

http://www.lisdn.com

http://www.lisdn.com

trees (text_buf[r]'th tree) and returns the longest-match position

and length via the global variables match_position and match_length.

If match_length = F, then removes the old node in favor of the new

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;

unsigned char *key;

cmp = 1; key = &text_buf[r]; p = N 1 key[0];

rson[r] = lson[r] = NIL; match_length = 0;

for ( ; ; ) {

if (cmp >= 0) {

http://www.lisdn.com

http://www.lisdn.com

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 > match_length) {

match_position = p;

if ((match_length = i) >= F) break;

}

http://www.lisdn.com

http://www.lisdn.com

}

dad[p] = NIL; /* remove p */

}

void DeleteNode(int p) /* deletes node p from tree */

{

int q;

if (dad[p] == NIL) return; /* not in tree */

http://www.lisdn.com

http://www.lisdn.com

if (rson[p] == NIL) q = lson[p];

else if (lson[p] == NIL) q = rson[p];

else {

q = lson[p];

if (rson[q] != NIL) {

do { q = rson[q]; } while (rson[q] != NIL);

lson[q] = lson[p]; dad[lson[p]] = q;

}

rson[q] = rson[p]; dad[rson[p]] = q;

}

http://www.lisdn.com

http://www.lisdn.com

}

void Encode(void)

{

int i, c, len, r, s, last_match_length, code_buf_ptr;

InitTree(); /* initialize trees */

code_buf[0] = 0; /* code_buf[1..16] saves eight units of code, and

code_buf[0] works as eight flags, "1" representing that the unit

is an unencoded letter (1 byte), "0" a position-and-length pair

(2 bytes). Thus, eight units require at most 16 bytes of code. */

http://www.lisdn.com

http://www.lisdn.com

s = 0; r = N - F;

for (i = s; i < r; i ) text_buf[i] = ' '; /* Clear the buffer with

any character that will appear often. */

for (len = 0; len < F && (c = getc(infile)) != EOF; len )

text_buf[r len] = c; /* Read F bytes into the last F bytes of

the buffer */

if ((textsize = len) == 0) return; /* text of size zero */

for (i = 1; i <= F; i ) InsertNode(r - i); /* Insert the F strings,

each of which begins with one or more 'space' characters. Note

the order in which these strings are inserted. This way,

degenerate trees will be less likely to occur. */

http://www.lisdn.com

http://www.lisdn.com

InsertNode(r); /* Finally, insert the whole string just read. The

global variables match_length and match_position are set. */

do {

if (match_length > len) match_length = len; /* match_length

may be spuriously long near the end of text. */

if (match_length <= THRESHOLD) {

match_length = 1; /* Not long enough match. Send one byte. */

code_buf[0] |= mask; /* 'send one byte' flag */

code_buf[code_buf_ptr ] = text_buf[r]; /* Send uncoded. */

} else {

code_buf[code_buf_ptr ] = (unsigned char) match_position;

code_buf[code_buf_ptr ] = (unsigned char)

(((match_position >> 4) & 0xf0)

http://www.lisdn.com

http://www.lisdn.com

| (match_length - (THRESHOLD 1))); /* Send position and

length pair. Note match_length > THRESHOLD. */

}

if ((mask < <= 1) == 0) { /* Shift mask left one bit. */

for (i = 0; i < code_buf_ptr; i ) /* Send at most 8 units of */

putc(code_buf[i], outfile); /* code together */

codesize = code_buf_ptr;

code_buf[0] = 0; code_buf_ptr = mask = 1;

}

last_match_length = match_length;

for (i = 0; i < last_match_length &&

(c = getc(infile)) != EOF; i ) {

http://www.lisdn.com

http://www.lisdn.com

DeleteNode(s); /* Delete old strings and */

text_buf[s] = c; /* read new bytes */

if (s < F - 1) text_buf[s N] = c; /* If the position is

near the end of buffer, extend the buffer to make

string comparison easier. */

s = (s 1) & (N - 1); r = (r 1) & (N - 1);

/* Since this is a ring buffer, increment the position

modulo N. */

InsertNode(r); /* Register the string in text_buf[r..r F-1] */

}

if ((textsize = i) > printcount) {

princ("ld\r", textsize); printcount = 1024;

/* Reports progress each time the textsize exceeds

http://www.lisdn.com

http://www.lisdn.com

multiples of 1024. */

}

while (i < last_match_length) { /* After the end of text, */

DeleteNode(s); /* no need to read, but */

s = (s 1) & (N - 1); r = (r 1) & (N - 1);

if (--len) InsertNode(r); /* buffer may not be empty. */

}

} while (len > 0); /* until length of string to be processed is zero */

if (code_buf_ptr > 1) { /* Send remaining code. */

for (i = 0; i < code_buf_ptr; i ) putc(code_buf[i], outfile);

codesize = code_buf_ptr;

}

http://www.lisdn.com

http://www.lisdn.com

printf("In : %ld bytes\n", textsize); /* Encoding is done. */

printf("Out: %ld bytes\n", codesize);

printf("Out/In: %.3f\n", (double)codesize / textsize);

}

void Decode(void) /* Just the reverse of Encode(). */

{

int i, j, k, r, c;

unsigned int flags;

for (i = 0; i < N - F; i ) text_buf[i] = ' ';

r = N - F; flags = 0;

for ( ; ; ) {

http://www.lisdn.com

http://www.lisdn.com

if (((flags >>= 1) & 256) == 0) {

if ((c = getc(infile)) == EOF) break;

flags = c | 0xff00; /* uses higher byte cleverly */

} /* to count eight */

if (flags & 1) {

if ((c = getc(infile)) == EOF) break;

putc(c, outfile); text_buf[r ] = c; r &= (N - 1);

} else {

if ((i = getc(infile)) == EOF) break;

if ((j = getc(infile)) == EOF) break;

i |= ((j & 0xf0) < < 4); j = (j & 0x0f) THRESHOLD;

for (k = 0; k <= j; k ) {

c = text_buf[(i k) & (N - 1)];

http://www.lisdn.com

http://www.lisdn.com

putc(c, outfile); text_buf[r ] = c; r &= (N - 1);

}

}

}

}

int main(int argc, char *argv[])

{

char *s;

if (argc != 4) {

printf("'lzss e file1 file2' encodes file1 into file2.\n"

"'lzss d file2 file1' decodes file2 into file1.\n");

http://www.lisdn.com

http://www.lisdn.com

return EXIT_FAILURE;

}

if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)

|| (s = argv[2], (infile = fopen(s, "rb")) == NULL)

|| (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {

printf("??? %s\n", s); return EXIT_FAILURE;

}

if (toupper(*argv[1]) == 'E') Encode(); else Decode();

fclose(infile); fclose(outfile);

return EXIT_SUCCESS; 网友回复:帮顶！ ！留着以后用 网友回复:mark 网友回复:mark 网友回复:收你们先，改天补回 网友回复:其实我更喜欢 C#的,C 不怎以懂,所以也没有认真看,希望以后会对我有所帮助!谢谢 [size=14px][/size]

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

http://www.lisdn.com

http://www.lisdn.com

/*

Problem

:

Weighted

Bipartite

Matching

Algorithm

:

Hungarian

Algorithm

Reference

:

Douglas

B.West,Introduction

to

Graph

Theory,125-129

Author

:

PC

Date

:

2005.2.23

*/

#include

<iostream.h>

#include

<iomanip.h>

#include

<fstream.h>

http://www.lisdn.com

http://www.lisdn.com

#include

<memory.h>

ifstream

fin("input.txt");

#define

cin

fin

const

int

max=50;

bool

T[max],R[max],visited[max];

int

U[max],V[max],gt[max][max],x[max],y[max];

int

N;

void

output()

{

http://www.lisdn.com

http://www.lisdn.com

int

i,j;

for(i=0;i<N;i )

{

for(j=0;j<N;j )

{

cout<<setw(2)<<gt[i][j]<<'

';

}

if(R[i])cout<<setw(2)<<'R'<<'

';

cout<<endl;

}

for(i=0;i<N;i )

if(T[i])cout<<setw(2)<<'T'<<'

';

else

cout<<setw(2)<<'

'<<'

';

http://www.lisdn.com

http://www.lisdn.com

cout<<endl;

}

int

path(int

u)

{

int

v;

for(v=0;v<N;v )

{

if(gt[u][v]==0

&&

!visited[v])

{

visited[v]=1;

if(y[v]<0

||

path(y[v]))

http://www.lisdn.com

http://www.lisdn.com

{

x[u]=v;y[v]=u;

R[u]=1;T[v]=0;

return

1;

}else{

T[v]=1;

R[y[v]]=0;

}

}

}

return

0;

}

http://www.lisdn.com

http://www.lisdn.com

int

main()

{

for(;cin>>N;){

int

i,j,ans,sigma,step=0;

for(i=0;i<N;i )

{

U[i]=V[i]=0;

for(j=0;j<N;j )

{

cin>>gt[i][j];

if(U[i]<gt[i][j])U[i]=gt[i][j];

}

http://www.lisdn.com

http://www.lisdn.com

}

for(i=0;i<N;i )

{

for(j=0;j<N;j )

{

gt[i][j]=U[i]-gt[i][j];

}

}

//////////////////////////////////////////////////////////

for(;;)

{

ans=0;

http://www.lisdn.com

http://www.lisdn.com

sigma=0;

memset(x,-1,sizeof(x));

memset(y,-1,sizeof(y));

memset(R,0,sizeof(R));

memset(T,0,sizeof(T));

for(i=0;i<N;i )

{

if(x[i]<0)

{

memset(visited,0,sizeof(visited));

ans =path(i);

}

http://www.lisdn.com

http://www.lisdn.com

for(j=0;j<N;j )

{

if(sigma<1

||

sigma>gt[i][j]

&&

gt[i][j]>0)

sigma=gt[i][j];

}

}

cout<<"step

"<<

step<<":\n";

output();

if(ans>=N)

break;

http://www.lisdn.com

http://www.lisdn.com

for(i=0;i<N;i )

{

if(!R[i])

U[i]-=sigma;

if(T[i])

V[i] =sigma;

for(j=0;j<N;j )

{

if(T[j])

gt[i][j] =sigma;

if(!R[i])

gt[i][j]-=sigma;

http://www.lisdn.com

http://www.lisdn.com

}

}

}

//////////////////////////////////////////////////////////

ans=0;

cout<<"Result:"<<endl;

for(i=0;i<N;i )

{

ans =U[i] V[i];

for(j=0;j<N;j )

{

if(x[i]==j

&&

y[j]==i)cout<<setw(2)<<U[i] V[j]<<'

';

else

cout<<setw(2)<<0<<'

';

http://www.lisdn.com

http://www.lisdn.com

}

cout<<endl;

}

cout<<"Maximum

:

"<<ans<<endl;

}

return

0;

}

input.txt:

5

http://www.lisdn.com

http://www.lisdn.com

4

1

6

2

3

5

0

3

7

6

2

3

4

5

8

3

4

6

3

4

4

6

5

8

6

5

4

4

4

3

6

1

1

4

3

4

1

4

5

3

5

5

6

4

7

9

5

3

6

8

3

http://www.lisdn.com

http://www.lisdn.com

5

7

8

9

8

7

8

7

6

7

6

9

6

5

4

6

8

5

7

6

4

7

6

5

5

5

5

1

2

3

4

5

6

7

8

7

2

1

3

4

4

5

3

6

2

8

7

http://www.lisdn.com

http://www.lisdn.com

4

1

3

5

4

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

/*

Problem

:

Weighted

Bipartite

Matching

Algorithm

:

Hungarian

Algorithm

http://www.lisdn.com

http://www.lisdn.com

Reference

:

Douglas

B.West,Introduction

to

Graph

Theory,125-129

Author

:

PC

Date

:

2005.2.23

*/

#include

<iostream.h>

#include

<iomanip.h>

#include

<fstream.h>

#include

<memory.h>

ifstream

fin("input.txt");

#define

cin

fin

http://www.lisdn.com

http://www.lisdn.com

const

int

max=50;

bool

T[max],R[max],visited[max];

int

U[max],V[max],gt[max][max],x[max],y[max];

int

N;

void

output()

{

int

i,j;

for(i=0;i<N;i )

{

for(j=0;j<N;j )

{

cout<<setw(2)<<gt[i][j]<<'

';

http://www.lisdn.com

http://www.lisdn.com

}

if(R[i])cout<<setw(2)<<'R'<<'

';

cout<<endl;

}

for(i=0;i<N;i )

if(T[i])cout<<setw(2)<<'T'<<'

';

else

cout<<setw(2)<<'

'<<'

';

cout<<endl;

}

int

path(int

u)

{

http://www.lisdn.com

http://www.lisdn.com

int

v;

for(v=0;v<N;v

)

{

if(U[u] V[v]-gt[u][v]==0

&&

!visited[v])

{

visited[v]=1;

if(y[v]<0

||

path(y[v]))

{

x[u]=v;y[v]=u;

R[u]=1;T[v]=0;

return

1;

}else{

T[v]=1;

http://www.lisdn.com

http://www.lisdn.com

R[y[v]]=0;

}

}

}

return

0;

}

int

main()

{

int

i,j,ans,sigma,step=0;

for(;cin>>N;){

for(i=0;i<N;i )

http://www.lisdn.com

http://www.lisdn.com

{

U[i]=V[i]=0;

for(j=0;j<N;j )

{

cin>>gt[i][j];

if(U[i]<gt[i][j])U[i]=gt[i][j];

}

}

//////////////////////////////////////////////////////////

for(;;)

{

ans=0;

sigma=0;

http://www.lisdn.com

http://www.lisdn.com

memset(x,-1,sizeof(x));

memset(y,-1,sizeof(y));

memset(R,0,sizeof(R));

memset(T,0,sizeof(T));

for(i=0;i<N;i )

{

if(x[i]<0)

{

memset(visited,0,sizeof(visited));

ans =path(i);

}

}

http://www.lisdn.com

http://www.lisdn.com

for(i=0;i<N;i )

{

if(!R[i])

for(j=0;j<N;j )

{

if(!T[j] V[j]-gt[i][j] && U[i] V[j]-gt[i][j]>0))

&&

(sigma<1

||

sigma>U[i]

sigma=U[i] V[j]-gt[i][j];

}

}

cout<<"step

"<<

step<<":\n";

output();

if(ans>=N)

http://www.lisdn.com

http://www.lisdn.com

break;

for(i=0;i<N;i )

{

if(!R[i])

U[i]-=sigma;

if(T[i])

V[i] =sigma;

}

}

/////////////////////////////////////////////////////////

ans=0;

http://www.lisdn.com

http://www.lisdn.com

cout<<"Result:"<<endl;

for(i=0;i<N;i )

{

ans =U[i] V[x[i]];

for(j=0;j<N;j )

{

if(x[i]==j

&&

y[j]==i)cout<<setw(2)<<U[i] V[j]<<'

';

else

cout<<setw(2)<<0<<'

';

}

cout<<endl;

}

cout<<"Maximum

:

"<<ans<<endl;

}

http://www.lisdn.com

http://www.lisdn.com

return

0;

}

http://www.lisdn.com

http://www.lisdn.com

void* memcpy( void *dst, const void *src, unsigned int len ) { register char *d; register char *s; if (len == 0) return dst; if ( dst > src ) //考虑覆盖情况 { d = (char *)dst len - 1; s = (char *)src len - 1; while ( len >= 4 ) //循环展开，提高执行效率 { *d-- = *s--; *d-- = *s--; *d-- = *s--; *d-- = *s--; len -= 4; } while ( len-- ) { *d-- = *s--; } } else if ( dst < src ) {

http://www.lisdn.com

http://www.lisdn.com

d = (char *)dst; s = (char *)src; while ( len >= 4 ) { *d = *s ; *d = *s ; *d = *s ; *d = *s ; len -= 4; } while ( len-- ) { *d = *s ; } } return dst; } 出现次数相当频繁 网友回复:1．常用的算法设计方法： 1.1 迭代法 1.2 穷举搜索法 1.3 递推法 1.4 递归法 1.5 贪婪法 1.6 分治法

http://www.lisdn.com

http://www.lisdn.com

1.7 动态规划法 1.8 回溯法 算法基础部分: 算法是对特定问题求解步骤的一种描述， 算法是指令的有限序列， 其中每一条指令表示一个 或多个操作。

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

1.1 迭代法：

（1）选一个方程的近似根，赋给变量 x0；

（2）将 x0 的值保存于变量 x1，然后计算 g(x1)，并将结果存于变量 x0；

（3）当 x0 与 x1 的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。

【算法】迭代法求方程的根

{

x0=初始近似根；

http://www.lisdn.com

http://www.lisdn.com

do {

x1=x0；

x0=g(x1)；

/*按特定的方程计算新的近似根*/

} while ( fabs(x0-x1)>Epsilon)；

printf(“方程的近似根是%f\n”，x0)；

}

X=（x0，x1，…，xn-1）

xi=gi(X)

(I=0，1，…，n-1)

【算法】迭代法求方程组的根

{

for (i=0;i<n;i )

http://www.lisdn.com

http://www.lisdn.com

x[i]=初始近似根;

do {

for (i=0;i<n;i )

y[i]=x[i];

for (i=0;i<n;i )

x[i]=gi(X);

for (delta=0.0,i=0;i<n;i )

if (fabs(y[i]-x[i])>delta)

delta=fabs(y[i]-x[i])；

} while (delta>Epsilon)；

for (i=0;i<n;i )

printf(“变量 x[%d]的近似根是 %f”，I，x[i])；

http://www.lisdn.com

http://www.lisdn.com

printf(“\n”)；

}

（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在 使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；

（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭 代失败。

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

http://www.lisdn.com

http://www.lisdn.com

1.2 穷举搜索法：

【问题】 将 A、B、C、D、E、F 这六个变量排成如图所示的三角形，这六个变量分别取[1， 6]上的整数， 且均不相同。 求使三角形三条边上的变量之和相等的全部解。 如图就是一个解。

# include <stdio.h>

void main()

{

int a,b,c,d,e,f;

for (a=1;a<=6;a )

//a,b,c,d,e 依次取不同的值

for (b=1;b<=6;b )

{ http://www.lisdn.com

http://www.lisdn.com

if (b==a)

continue;

for (c=1;c<=6;c )

{

if (c==a)||(c==b)

continue;

for (d=1;d<=6;d )

{

if (d==a)||(d==b)||(d==c)

continue;

for (e=1;e<=6;e )

{

if (e==a)||(e==b)||(e==c)||(e==d) continue;

f=21-(a b c d e);//最后一个用减法算

if ((a b c==c d e))&&(a b c==e f a))

{

printf(“m,a);

printf(“MM”,b,f);

printf(“-MM”,c,d,e);

http://www.lisdn.com

http://www.lisdn.com

scanf(“%c”);

}

}

}

}

}

}

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

1.3 递推法：

【问题】 阶乘计算

N=a[m]×10m-1 a[m-1]×10m-2 …

a[2]×101 a[1]×100

http://www.lisdn.com

http://www.lisdn.com

3

0

2

1

……

# include <stdio.h>

# include <malloc.h>

# define

MAXN

1000

void pnext(int a[ ],int k)//已知 a 中的（k-1）!,求出 k！在 a 中。

{

int *b,m=a[0],i,j,r,carry;

b=(int * ) malloc(sizeof(int)* (m 1));

for ( i=1;i<=m;i )

b[i]=a[i];

for ( j=1;j<k;j )

//控制累加 k-1 次

http://www.lisdn.com

http://www.lisdn.com

{

for ( carry=0,i=1;i<=m;i )//i 存放的是整数的位数

{

r=(i<a[0]?a[i] b[i]:a[i]) carry;//进位标志

a[i]=r;

carry=r/10;

}

if (carry) a[

m]=carry;

}

free(b);

a[0]=m;

}

void write(int *a,int k)//功能是输出累加 K 次后的数组的各个位

{

int i;

http://www.lisdn.com

http://www.lisdn.com

printf(“M！=”,k);

for (i=a[0];i>0;i--)

printf(“%d”,a[i]);

printf(“\n\n”);

}

void main()

{

int a[MAXN],n,k;

printf(“Enter the number n: “);

scanf(“%d”,&n);

a[0]=1;

a[1]=1;

write(a,1);

for (k=2;k<=n;k )

http://www.lisdn.com

http://www.lisdn.com

{

pnext(a,k);

write(a,k);//输出长整数的各位

getchar();

}

}

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

http://www.lisdn.com

http://www.lisdn.com

1.4 递归法

【问题】编写计算斐波那契（Fibonacci）数列的第 n 项函数 fib（n） 。斐波那契数列为：0、 1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1) fib(n-2)

（当 n>1 时） 。

int fib(int n)

{

http://www.lisdn.com

http://www.lisdn.com

if (n==0)

return 0;

if (n==1)

return 1;

if (n>1)

return fib(n-1) fib(n-2);

}

【问题】背包问题

http://www.lisdn.com

http://www.lisdn.com

（1）考虑物品 i 被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。 选中后，继续递归去考虑其余物品的选择。

（2） 考虑物品 i 不被选择， 这种可能性仅当不包含物品 i 也有可能会找到价值更大的方案的 情况。

try(物品 i，当前选择已达到的重量和，本方案可能达到的总价值 tv)

{

/*考虑物品 i 包含在当前方案中的可能性*/

if(包含物品 i 是可以接受的)

{

http://www.lisdn.com

http://www.lisdn.com

if (i<n-1)

try(i 1,tw 物品 i 的重量,tv);

else

/*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/

}

/*考虑物品 i 不包含在当前方案中的可能性*/

if (不包含物品 i 仅是可考虑的)

if (i<n-1)

try(i 1,tw,tv-物品 i 的价值)；

else

http://www.lisdn.com

http://www.lisdn.com /*又一个完整方案，因它比前面的方案好，以它作为最佳方

}

0

1

2

3

5

3

2

1

4

4

3

1

http://www.lisdn.com

http://www.lisdn.com

C/C code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

Try(物品号，总重，价值)

【程序】

# include <stdio.h>

# define

N

100

double

limitW,totV,maxV;

int

option[N],cop[N];

http://www.lisdn.com

http://www.lisdn.com

struct

{

double

weight;

double

value;

}a[N];

int

n;

void find(int i,double tw,double tv)

{

int k;

/*考虑物品 i 包含在当前方案中的可能性*/

if (tw a[i].weight<=limitW)

{

cop[i]=1;

if (i<n-1) find(i 1,tw a[i].weight,tv);

else

{

for (k=0;k<n;k )

http://www.lisdn.com

http://www.lisdn.com option[k]=cop[k];

maxv=tv;

}

cop[i]=0;

}

/*考虑物品 i 不包含在当前方案中的可能性*/

if (tv-a[i].value>maxV)

if (i<n-1) find(i 1,tw,tv-a[i].value);

else

{

for (k=0;k<n;k )

option[k]=cop[k];

maxv=tv-a[i].value;

}

http://www.lisdn.com

http://www.lisdn.com

}

void main()

{

int k;

double w,v;

printf(“输入物品种数\n”);

scanf((“%d”,&n);

printf(“输入各物品的重量和价值\n”);

for (totv=0.0,k=0;k<n;k )

{

scanf(“”,&w,&v);

a[k].weight=w;

a[k].value=v;

totV =V;

http://www.lisdn.com

http://www.lisdn.com

}

printf(“输入限制重量\n”);

scanf(“”,&limitV);

maxv=0.0;

for (k=0;k<n;k ) cop[k]=0;

find(0,0.0,totV);

for (k=0;k<n;k )

if (option[k])

printf(“M”,k 1);

printf(“\n 总价值为%.2f\n”,maxv);

}

http://www.lisdn.com

http://www.lisdn.com

1． 当该物品被包含在候选解中依旧满足解的总重量的限制， 该物品被包含在候选解中是 应该继续考虑的；

2．

3． 仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时， 才去考虑该物品不被包括在候选解中；

4．

5．

【程序】

# include <stdio.h>

# define

N

100

double

limitW;

int

cop[N];

struct

ele

{

double

weight;

double

value;

http://www.lisdn.com

http://www.lisdn.com

} a[N];

int

k,n;

struct

{

int

flg;

double

tw;

double

tv;

}twv[N];

void next(int i,double tw,double tv)

{

twv[i].flg=1;

twv[i].tw=tw;

twv[i].tv=tv;

}

double find(struct ele *a,int n)

{

int i,k,f;

http://www.lisdn.com

http://www.lisdn.com

double maxv,tw,tv,totv;

maxv=0;

for (totv=0.0,k=0;k<n;k )

totv =a[k].value;

next(0,0.0,totv);

i=0;

While (i>=0)

{

f=twv[i].flg;

tw=twv[i].tw;

tv=twv[i].tv;

switch(f)

{

case 1:

twv[i].flg ;

http://www.lisdn.com

http://www.lisdn.com if (tw a[i].weight<=limitW)

if (i<n-1)

{

next(i 1,tw a[i].weight,tv);

i ;

}

else

{

maxv=tv;

for (k=0;k<n;k )

cop[k]=twv[k].flg!=0;

}

break;

case 0:

i--;

break;

http://www.lisdn.com

http://www.lisdn.com

default:

twv[i].flg=0;

if (tv-a[i].value>maxv)

if (i<n-1)

{

next(i 1,tw,tv-a[i].value);

i ;

}

else

{

maxv=tv-a[i].value;

for (k=0;k<n;k )

cop[k]=twv[k].flg!=0;

}

break;

http://www.lisdn.com

http://www.lisdn.com

}

}

return maxv;

}

void main()

{

double maxv;

printf(“输入物品种数\n”);

scanf((“%d”,&n);

printf(“输入限制重量\n”);

scanf(“”,&limitW);

printf(“输入各物品的重量和价值\n”);

for (k=0;k<n;k )

scanf(“”,&a[k].weight,&a[k].value);

http://www.lisdn.com

http://www.lisdn.com

maxv=find(a,n);

printf(“\n 选中的物品为\n”);

for (k=0;k<n;k

)

if (option[k])

printf(“M”,k 1);

printf(“\n 总价值为%.2f\n”,maxv);

}

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.lisdn.com

http://www.lisdn.com

http://www.CodeHighlighter.com/

1.5 贪婪法

1. 不能保证求得的最后解是最佳的；

2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

while 能朝给定总目标前进一步 do

http://www.lisdn.com

http://www.lisdn.com

【问题】装箱问题

{

http://www.lisdn.com

http://www.lisdn.com

for (i=0;i<n;i )

{

if （已用箱子都不能再放物品 i）

{

box_count ；

}

else

}

http://www.lisdn.com

http://www.lisdn.com

}

【程序】

# include <stdio.h>

# include <stdlib.h>

typedef struct ele

{

int vno;

}

ELE;

typedef struct hnode

http://www.lisdn.com

http://www.lisdn.com

{

int remainder;

Struct hnode *next;

}

HNODE;

void main()

{

int n, i, box_count, box_volume, *a;

HNODE *box_h, *box_t, *j;

ELE

*p, *q;

Printf(“输入箱子容积\n”);

Scanf(“%d”,&box_volume);

Printf(“输入物品种数\n”);

Scanf(“%d”,&n);

http://www.lisdn.com

http://www.lisdn.com

A=(int *)malloc(sizeof(int)*n);

Printf(“请按体积从大到小顺序输入各物品的体积：”);

For (i=0;i<n;i )

scanf(“%d”,a i);

Box_h=box_t=NULL;

Box_count=0;

For (i=0;i<n;i )

{

p=(ELE *)malloc(sizeof(ELE));

p->vno=i;

for (j=box_h;j!=NULL;j=j->next)

if (j->remainder>=a[i])

break;

if (j==NULL)

{

j=(HNODE *)malloc(sizeof(HNODE));

j->remainder=box_volume-a[i];

http://www.lisdn.com

http://www.lisdn.com

if (box_h==NULL)

box_h=box_t=j;

else

box_t=boix_t->next=j;

j->next=NULL;

box_count ;

}

else j->remainder-=a[i];

if (q==NULL)

{

}

http://www.lisdn.com

http://www.lisdn.com

else

{

}

}

printf(“共使用了%d 只箱子”，box_count);

printf(“各箱子装物品情况如下：”);

for (j=box_h,i=1;j!=NULL;j=j->next,i )

{

printf(“第-只箱子，还剩余容积 M，所装物品有；\n”,I,j->remainder);

printf(“M”,p->vno 1);

printf(“\n”);

}

http://www.lisdn.com

http://www.lisdn.com

}

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

1.6 分治法

1．分治法的基本思想

http://www.lisdn.com

http://www.lisdn.com

2．分治法的适用条件

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

（3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

http://www.lisdn.com

http://www.lisdn.com

3．分治法的基本步骤

（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

（2）求解：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；

（3）合并：将各个子问题的解合并为原问题的解。

Divide_and_Conquer（P）

if |P|≤n0

http://www.lisdn.com

http://www.lisdn.com

for i←1 to k

do

yi ← Divide-and-Conquer（Pi）

△ 递归解决 Pi

T ← MERGE（y1，y2，…，yk）

△ 合并子问题

Return（T）

【问题】循环赛日程表

http://www.lisdn.com

http://www.lisdn.com

（1）每个选手必须与其他 n-1 个选手各赛一次；

（2）每个选手一天只能参赛一次；

（3）循环赛在 n-1 天内结束。

1 4 5 6 7

2

3

1 5 6 7 8

2

3

4

2 6 7 8 5

1

4

3

3

4

1

2

http://www.lisdn.com

http://www.lisdn.com

7

8

5

6

1 8 5 6 7

2

3

4

3

2

1

1 1 4 3 2

2

3

4

5

6

7

8

2

1 1

2 4 3

1

4

3

6

5

8

7

1 3

2 2

3 1 4

4

1

2

7

8

5

6

2 4

1 3

4 2 1

3

2

1

8

7

6

5

（1）

（2）

（3）

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

1.7 动态规划法

◆动态规划的适用条件

http://www.lisdn.com

http://www.lisdn.com

（1）最优化原理（最优子结构性质）

（2）无后向性

（3）子问题的重叠性

http://www.lisdn.com

http://www.lisdn.com

◆动态规划的基本思想

http://www.lisdn.com

http://www.lisdn.com

3、动态规划算法的基本步骤

（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段 一定要是有序的或者是可排序的（即无后向性） ，否则问题就无法用动态规划求解。

（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。 当然，状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有 着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果 我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻 两段的各状态之间的关系来确定决策。

（4） 写出规划方程 （包括边界条件） 动态规划的基本方程是规划方程的通用形式化表达式。 ：

http://www.lisdn.com

1. 对 fn 1(xn 1)初始化;

{边界条件}

for k:=n downto 1 do

for 每一个 xk∣Xk do

for 每一个 uk∣Uk(xk) do

begin

fk(xk):=一个极值;

{∞或－∞}

xk 1:=Tk(xk,uk);

{状态转移方程}

t:=φ(fk 1(xk 1),vk(xk,uk));

{基本方程(9)式}

if

t 比 fk(xk)更优 then fk(xk):=t; {计算 fk(xk)的最优值}

end;

t:=一个极值;

{∞或－∞}

http://www.lisdn.com

http://www.lisdn.com

for 每一个 x1∣X1 do

if f1(x1)比 t 更优 then t:=f1(x1);

{按照 10 式求出最优指标}

（1）分析最优解的性质，并刻划其结构特征。

（2）递归地定义最优值。

（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。

（4）根据计算最优值时得到的信息，构造一个最优解。

【问题】凸多边形的最优三角剖分问题

http://www.lisdn.com

http://www.lisdn.com

(a)

(b)

http://www.lisdn.com

http://www.lisdn.com

（1）最优子结构性质

（2）最优三角剖分对应的权的递归结构

t[i，j]的值可以利用最优子结构性质递归地计算。由于退化的 2 顶点多边形的权值为 0，所 以 t[i，i]=0，i=1，2，…，n 。当 j 一 i≥1 时，子多边形<vi-1，vi，…，vj>至少有 3 个顶点。 由最优于结构性质，t[i，j]的值应为 t[i，k]的值加上 t[k 1，j]的值，再加上△vi-1vkvj 的权值， 并在 i≤k≤j-1 的范围内取最小。由此，t[i，j]可递归地定义为：

（3）计算最优值

http://www.lisdn.com

http://www.lisdn.com

Procedure MINIMUM_WEIGHT(P，w)；

Begin

n=length[p]-1;

for i=1 to n do

t[i,i]:=0;

for ll=2 to n do

for i=1 to n-ll 1 do

begin

j=i ll-1;

t[i,j]=∞;

for k=i to j-1 do

http://www.lisdn.com

http://www.lisdn.com

begin

q=t[i,k] t[k 1,j] ω(△vi-1vkvj);

if q<t[i,j] then

begin

t[i,j]=q;

s[i,j]=k;

end;

end;

end;

return(t,s);

end;

（4）构造最优三角剖分

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

1.8 回溯法

http://www.lisdn.com

http://www.lisdn.com

1、回溯法的一般描述

http://www.lisdn.com

http://www.lisdn.com

1.9 分支定界法：

http://www.lisdn.com

http://www.lisdn.com

1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活

2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找

E-节点是具有最大收益的活节点。

2．几个重要的算法程序

2.1 堆排序

http://www.lisdn.com

http://www.lisdn.com

template

void HeapSort ( Elem R[], int n ) {

// 对记录序列 R[1..n]进行堆排序。

for ( i=n/2; i>0; --i )

// 把 R[1..n]建成大顶堆

HeapAdjust ( R, i, n );

for ( i=n; i>1; --i ) {

R[1]←→R;

// 将堆顶记录和当前未经排序子序列

http://www.lisdn.com

http://www.lisdn.com

// R[1..i]中最后一个记录相互交换

// 将 R[1..i-1] 重新调整为大顶堆

}

} // HeapSort

Template

void HeapAdjust (Elem R[], int s, int m) {

// 已知 R[s..m]中记录的关键字除 R[s].key 之

// 外均满足堆的定义，本函数调整 R[s] 的关

// 键字，使 R[s..m]成为一个大顶堆（对其中

// 记录的关键字而言）

rc = R[s];

http://www.lisdn.com

http://www.lisdn.com

for ( j=2*s; j<=m; j*=2 ) {// 沿 key 较大的孩子结点向下筛选

if ( j

if ( rc.key >= R[j].key )

break; // rc 应插入在位置 s 上

R[s] = R[j];

s = j;

}

R[s] = rc; // 插入

1. 对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为 2(k-1);

2．对 n 个关键字，建成深度为 1)?log2n?h(=的堆，所需进行的关键字比较的次数至多为 4n;

3. 调整“堆顶”n-1 次，总共进行的关键字比较的次数不超过

?2(log2(n-1)

… log22)?log2(n-2)?<log2n?2n(

http://www.lisdn.com

http://www.lisdn.com

2.2 归并排序

“归并”算法描述如下：

template

void Merge (Elem SR[], Elem TR[], int i, int m, int n) {

// 将有序的 SR[i..m]和 SR[m 1..n]归并为

// 有序的 TR[i..n]

for (j=m 1, k=i; i<=m && j<=n;

k)

{

// 将 SR 中记录由小到大地并入 TR

if (SR.key<=SR[j].key) TR[k] = SR[i ];

else TR[k] = SR[j ];

http://www.lisdn.com

http://www.lisdn.com

}

if (i<=m) TR[k..n] = SR[i..m];

// 将剩余的 SR[i..m]复制到 TR

if (j<=n) TR[k..n] = SR[j..n];

// 将剩余的 SR[j..n]复制到 TR

} // Merge

template

void Msort ( Elem SR[], Elem TR1[], int s, int t ) {

// 将 SR[s..t]进行 2-路归并排序为 TR1[s..t]。

http://www.lisdn.com

http://www.lisdn.com

if (s==t) TR1[s] = SR[s];

else {

m = (s t)/2;

// 将 SR[s..t]平分为 SR[s..m]和 SR[m 1..t]

Msort (SR, TR2, s, m);

// 递归地将 SR[s..m]归并为有序的 TR2[s..m]

Msort (SR, TR2, m 1, t);

//递归地 SR[m 1..t]归并为有序的 TR2[m 1..t]

Merge (TR2, TR1, s, m, t);

// 将 TR2[s..m]和 TR2[m 1..t]归并到 TR1[s..t]

}

} // MSort

http://www.lisdn.com

http://www.lisdn.com

template

void MergeSort (Elem R[]) {

// 对记录序列 R[1..n]作 2-路归并排序。

MSort(R, R, 1, n);

} // MergeSort

1. 按平均的时间性能来分，有三类排序方法：

http://www.lisdn.com

http://www.lisdn.com

2. 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到 O(n)的时间复杂 度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为 O(n2)，因此是应该尽 量避免的情况。

3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为 O(1)；

2. 快速排序为 O(logn)，为栈所需的辅助空间;

3. 归并排序所需辅助空间最多，其空间复杂度为 O(n);

4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。

http://www.lisdn.com

http://www.lisdn.com

for(int i = 1; i < n; i < <= 1) { int j = 0; for(; 2*i j - 1 < n; j = 2*i) {

http://www.lisdn.com

http://www.lisdn.com

int low = j; int mid = j i - 1; int high = j 2*i -1; int k = 0; int m = mid 1; while(low <= mid && m <= high) { if(ele[low] < ele[m]) temp [k ] = ele[low ]; else temp[k ] = ele[m ]; } while(low <= mid) temp[k ] = ele[low ]; while(m <= high) temp[k ] = ele[m ]; while(k > 0) ele[high--] = temp[--k]; } if(i j < n) { int low = j; int mid = j i - 1; int high = n - 1; int k = 0; int m = mid 1; while(low <= mid && m <= high) { if(ele[low] < ele[m]) temp [k ] = ele[low ]; else temp[k ] = ele[m ];

http://www.lisdn.com

http://www.lisdn.com

} while(low <= mid) temp[k ] = ele[low ]; while(m <= high) temp[k ] = ele[m ]; while(k > 0) ele[high--] = temp[--k]; } } 网友回复:收藏 网友回复:haotie 网友回复:数组可以那样定义吗 网友回复:顶了 网友回复:好贴，mark 网友回复: 哦!楼主好像在讲数据结构是不是！ 收藏了，谢谢！ 网友回复:mark!!!!!! 不过我也发个很简单的大数啊~

C/C code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

http://www.lisdn.com

http://www.lisdn.com

/*效率低下的算法*/

#include <stdio.h>

#define N 10

int main(void)

{

int i, j, m, c, t, a[1000];

a[0]=1;

m=1;

for(i=1; i<=N; i )

/*i, n 用于控制数值*/

http://www.lisdn.com

http://www.lisdn.com

{

for(j=0, c=0; j<m; j )

/*j, m 控制数位*/

{

t=a[j]*i c;

a[j]=t;

c=t/10;

}

for(; c;)

/*当有进位情况时*/

{

a[m ]=c;

c/=10;

}

}

http://www.lisdn.com

http://www.lisdn.com

for(i=m-1; i>=0; i--)

{

printf("%d",a[i]);

}

getch();

return 0;

}

http://www.lisdn.com

http://www.lisdn.com

C/C code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

int * ShellSort(int * array,int num)

{

int d=num;

while(d>1)

{

http://www.lisdn.com

http://www.lisdn.com

d=(d 1)/2;

for(int i=d;i<num;i )

{

if(array[i]<array[i-d])

{

int tmp=array[i];

for(int j=i-d;j>=0&&tmp<array[j];j-=d)

array[j d]=array[j];

array[j d]=tmp;

}

}

}

return array;

http://www.lisdn.com

http://www.lisdn.com

}

VS2008 中编译运行，加上必要的头文件就行。

C/C code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

http://www.lisdn.com

http://www.lisdn.com

typedef int dataType;

int arraySize = 0; //全局数组大小

int _tmain(int argc, _TCHAR* argv[])

{

void MergeSort(dataType *ptrArray);

void MergePass(dataType *ptrA, dataType *ptrB, int s);

void Merge(dataType *ptrA, dataType *ptrB, int begin, int mid, int end);

//////////////////////////////////////////////////////////////////////////

http://www.lisdn.com

http://www.lisdn.com

dataType intArray[7] = {3, 6, 4, 12, 8, 5, 14};

arraySize = sizeof(intArray) / sizeof(dataType);

MergeSort(intArray);

for(int i = 0; i != 7;

i){

printf("%d ",intArray[i]);

}

printf("\n");

http://www.lisdn.com

http://www.lisdn.com

return 0;

}

/********************************************************************/

/*如何合并？

*/

/*两手各指着（已排好的）左右两堆的最小数据，取出两者中较小的一个后，*/

/*随即指向那一堆的手移向下一层的数据，

*/

/*永远不必翻下面的数据，只需要盯着最上面的两个数据

*/

/********************************************************************/

void Merge(dataType *ptrA, dataType *ptrB, int begin, int mid, int end)

{

http://www.lisdn.com

http://www.lisdn.com

int i = begin, k = begin;

int j = mid

1;

while(i <= mid && j <= end){

if(ptrA[i] < ptrA[j])

ptrB[k ] = ptrA[i ];

else

ptrB[k ] = ptrA[j ];

}

if (i > mid)

while (j <= end)

ptrB[k ] = ptrA[j ];

else

http://www.lisdn.com

http://www.lisdn.com

while (i <= mid)

ptrB[k ] = ptrA[i ];

}

/********************************/

/*对相邻为 s 的一段序列排序

*/

/*3 6 4 12 8

5

14

*/

/* [3,6] [4,12] [5,8] [14]

*/

/*[3,4,6,12][5,8,14]

*/

/*[3,4,5,6,8,12,14]

*/

/********************************/

http://www.lisdn.com

http://www.lisdn.com

void MergePass(dataType *ptrA, dataType *ptrB, int s)

{

int i;

for (i = 0; i <= arraySize - 2 * s; i = 2 * s){

//合并大小为 s 的相邻二段子数组

Merge(ptrA, ptrB, i, i

s - 1, i

2 * s - 1);

}

//剩下的元素个数小于 2s

if ((i

s) < arraySize)

Merge(ptrA, ptrB, i, i

s - 1, arraySize - 1);

else

while(i != arraySize){

http://www.lisdn.com

http://www.lisdn.com

ptrB[i] = ptrA[i];

i ;

}

}

void MergeSort(dataType *ptrA)

{

dataType *ptrB = (dataType *)malloc(arraySize * sizeof(dataType));

int i = 1;

while(i < arraySize){

MergePass(ptrA, ptrB, i); //合并到数组 b

http://www.lisdn.com

http://www.lisdn.com

i = i;

MergePass(ptrB, ptrA, i); //合并到数组 a

i = i;

}

free(ptrB);

}

http://www.lisdn.com

http://www.lisdn.com

#include <stdio.h> #include <iostream> #include <iomanip>

http://www.lisdn.com

http://www.lisdn.com

using namespace std;

int Partition(int a[],int low,int high) { int b=a[low]; int x,y;

while(low!=high) { while(low <high&&b <a[high]) { --high;}

x=a[low]; a[low]=a[high];a[high]=x;

while(low <high&&b>a[low]) { low;}

y=a[low]; a[low]=a[high];a[high]=y; } return high;

}

void QuickSort(int a[],int l,int h)

http://www.lisdn.com

http://www.lisdn.com

{ if(l <=h) { int op=Partition(a,l,h); QuickSort(a,l,op-1); QuickSort(a,op 1,h);

} }

void main() { int q[10]={21,93,24,11,78,7,12,13,19,81}; QuickSort(q,0,10); int j; for(j=0;j <10;j ) cout < <q[j] < <setw(5); getchar();

}

http://www.lisdn.com

http://www.lisdn.com

// 伪线性 时间复杂度 O(C*n)

int maxf(int a,int b) //求最大值函数 { if(a>=b) return a; else return b; }

int KapSack(int x[],const int e[],const int w[],const int n,const int c) { int i,j; int v[n 1][c 1];

for(i=0;i <=n;i ) // 初始化第一行 为 0 v[i][0]=0; for(j=0;j <=c;j ) //初始化第一列 为 0 v[0][j]=0;

/* for(i=0;i <n 1;i ) //也可以 完全初始化 v[i][j]数组 均为 0 for(j=0;j <c 1;j ) v[i][j]=0;*/

for(i=1;i <=n;i )

http://www.lisdn.com

http://www.lisdn.com

for(j=1;j <=c;j ) { if(w[i]>j) v[i][j]=v[i-1][j]; else v[i][j]=maxf(v[i-1][j],v[i-1][j-w[i]] e[i]); }

j=c; for(i=n;i>0;i--) { if(v[i][j]>v[i-1][j]) {x[i]=1; j=j-w[i]; } else x[i]=0; }

for(i=0;i <=n;i ) //输出 v[i][j]数组 for(j=0;j <=c;j ) { cout < <v[i][j] < <" "; if(j==c) cout < <endl < <endl; } }

http://www.lisdn.com

http://www.lisdn.com

void main() { int e[6]={0,6,3,5,4,6}; int w[6]={0,2,2,6,5,4}; int x[6]; int n=5,c=10;

KapSack(x,e,w,n,c);

for(int k=1;k <=n;k ) cout < <x[k] < <endl; getchar(); }

int find(const int b[][6],const int v[],const int i) { int t=0; //1 b[i][0]; for(t=1 b[i][0];t <6;t ) { if(b[i][t]==1&&v[t]==0) return t;

http://www.lisdn.com

http://www.lisdn.com

else continue;

} return 0; }

bool v_is_full(const int v[]) { int i; for(i=1;i <6;i ) { if(v[i]==0) //不满 return false; } return true; }

int main() { int i,j,k,m; bool firsttime=true; int v[6]={0,0,0,0,0,0}; int a[6][6]={0,0,0,0,0,0, 0,0,1,0,1,0, 0,1,0,1,0,1,

http://www.lisdn.com

http://www.lisdn.com

0,0,1,0,1,1, 0,1,0,1,0,1, 0,0,1,1,1,0};

for(i=0;i <6;i ) for(j=0;j <6;j ) { cout < <a[i][j] < <" "; if(j==5) cout < <endl; }

cout < <"请输入起始结点(1--5)：" < <endl; cin>>m; a[m][0]=10; i=m;

v[i]=1;

while(a[m][0]!=0) //回溯的隐式判定条件，针对跳跃回溯 { if(firsttime==true) { a[m][0]=0; firsttime=false; }

k=find(a,v,i);

http://www.lisdn.com

http://www.lisdn.com

if(k!=0||(k==0&&v_is_full(v)&&a[i][m]==1)) //存在解，把 k 结点加入 { if(k==0&&v_is_full(v)&&a[i][m]==1) { a[i][0]=m; for(int l=1;l <6;l ) cout < <a[l][0] < <" "; cout < <endl;

v[i]=0; a[i][0]=0; i=a[0][i]; // return 0; // 只求一个解 } else //部分解 { a[i][0]=k; //加入解集 v[k]=1; //标记 k 已经被访问过 a[0][k]=i; //记录回溯时的位置 i=k;

} }

else //if(k==0) //&&v_is_full(v)==false)

http://www.lisdn.com

http://www.lisdn.com

{ v[i]=0; a[i][0]=0; i=a[0][i]; }

}

cin.get(); return 1;

} 网友回复:顶！ 网友回复:MARK 下 网友回复:二分搜索的递归与非递归

C/C code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

http://www.lisdn.com

http://www.lisdn.com

bool binarySearch(vector<int>& a, int data, int low, int high, int& count){

static bool flag=false;

int middle=(low high)/2;

cout<<a[middle]<<" ";

count ;

if(low<=high){

if(data<a[middle])

binarySearch(a, data, low,middle-1,count);

else if(data>a[middle])

binarySearch(a, data, middle 1,high, count);

else flag=true;

http://www.lisdn.com

http://www.lisdn.com

}

return flag;

}

bool binarySearch2(vector<int>& a, int data, int& count){

int low=0, high=a.size()-1;

int middle=(low high)/2;

while(low<=high){

cout<<a[middle]<<" ";

count ;

if(data<a[middle])

high=middle-1;

http://www.lisdn.com

http://www.lisdn.com

else if(data>a[middle])

low=middle 1;

else return true;

middle=(low high)/2;

}

return false;

}

C/C code

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

void insertionSort(vector<int>& a){

for(int i=1;i<a.size();i ){

int temp=a[i];

int j;

for(j=i-1; j>=0;j--){

if(temp<a[j])

a[j 1]=a[j];

else break;

http://www.lisdn.com

http://www.lisdn.com

}

a[j 1]=temp;

}

}

void insertionSort(int *a,int item,int size)

{

if(size==0)

a[0]=item;

else

{

for(int i=size-1;i>=0;i--)

{

if(item<a[i])

http://www.lisdn.com

http://www.lisdn.com

a[i 1]=a[i];

else

break;

}

a[i 1]=item;

size--;

insertionSort(a,a[size],size);

}

}

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

【问题】编写计算斐波那契（Fibonacci）数列的第 n 项函数 fib（n） 。斐波那契数列为：0、 1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1) fib(n-2)

（当 n>1 时） 。

http://www.lisdn.com

http://www.lisdn.com

# include <stdio.h>

long Fibonacci(long first, long second, long n );//递归的方法

long Fibonacci_(long first, long second, long n );//递推的方法

void main()

{

long a = 0, b = 1, c = 45;

for(long i = 0; i <= c; i )

{

printf("i=%ld.c=%ld,Fibonacci_=%ld\n", i,c, Fibonacci_(a, b, i));

}

http://www.lisdn.com

http://www.lisdn.com

for(long i = 0; i <= c; i )

{

printf("i=%ld.c=%ld,Fibonacci=%ld\n", i,c, Fibonacci(a, b, i));

}

getchar();

}

long Fibonacci(long first, long second, long n)//递归的方法

{

if(0 == n)

return first;

else if(1 == n)

http://www.lisdn.com

http://www.lisdn.com

return second;

else

{

return Fibonacci(first,second,(n - 1)) Fibonacci(first,second,(n - 2));

}

}

long Fibonacci_(long first, long second, long n )//递推的方法

{

long a = 0, b = 1, c = 0;

if(0 == n)

return first;

else if(1 == n)

http://www.lisdn.com

http://www.lisdn.com

return second;

else

{

for(long i = 0; i <= (n - 2); i )

{

c = a b;

a = b;

b = c;

}

return c;

}

}

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

http://www.lisdn.com

for( i = 0; i < len; i ) { int tmp = a[i]; for( j = i-1; j >=0 && a[j] > tmp; j --) a[j 1] = a[j];

a[j 1] = tmp; } }

////////////////////////////////////////////////////////////////////////// // 选择排序 void SelectSort(int a[], int len){ int i, j, tmp;

for( i = 0; i < len; i ) for( j = i 1; j < len; j ) if( a[i] > a[j] ){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }

http://www.lisdn.com

http://www.lisdn.com

////////////////////////////////////////////////////////////////////////// // 冒泡排序 void BubbleSort(int a[], int len) { int i, j, tmp;

for( i = 0; i < len; i ) for( j = len - 1; j > i; j --) if( a[j] < a[j-1] ){ tmp = a[j]; a[j] = a[j-1]; a[j - 1] = tmp; }

}

////////////////////////////////////////////////////////////////////////// // 折半插入排序 void BinaryInsert(int a[], int len){ int i, j, k, tmp;

for( i = 1; i < len; i ){ int left = 0, right = i - 1; while( left <= right ){ j = (left right)/2;

http://www.lisdn.com

http://www.lisdn.com

if(a[j] > a[i]) right = j - 1; else left = j 1; }

tmp = a[i]; for( k = i; k > left; k --) a[k] = a[k-1];

a[left] = tmp; } }

////////////////////////////////////////////////////////////////////////// // Shell 排序 void ShellSort(int a[], int len){ int i, j, tmp, gap; gap = len/2;

while( gap ){ for( i = gap; i < len; i ){ tmp = a[i]; // 对每一个 gap 插入排序 for( j = i; j >= gap && tmp < a[j-gap]; j -= gap)

http://www.lisdn.com

http://www.lisdn.com

a[j] = a[j-gap];

a[j] = tmp; }

gap = gap == 2?1:(int)(gap/2); } } // //Shell 排序 ///////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////// // 合并排序 // // a[p, q] 和 a[q 1, r]都是已经排好序的两个数组 // void merge(int a[], int p, int q, int r){ int n1 = q - p 1; int n2 = r - q; int *L = new int[n1]; int *R = new int[n2]; int i,j,k;

for( i = 0; i < n1; i ) L[i] = a[p i];

http://www.lisdn.com

http://www.lisdn.com

for( i = 0; i < n2; i ) R[i] = a[q 1 i];

for( k = p, i = j = 0; k <= r && i < n1 && j < n2; k ) if( L[i] < R[j] ) a[k] = L[i ]; else a[k] = R[j ];

if( i < n1 ) for( ; k <= r;) a[k ] = L[i ]; else if ( j < n2) for( ; k <= r;) a[k ] = R[j ];

delete []L; delete []R; }

void _imerge_sort(int a[], int p, int r){ if( p < r ){ int q = (p r)/2; _imerge_sort(a, p, q); _imerge_sort(a, q 1, r); merge(a, p, q, r);

http://www.lisdn.com

http://www.lisdn.com

} } void merge_sort(int a[], int len){ _imerge_sort(a, 0, len - 1); } // // 合并排序 //////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////// // 堆排序 // typedef struct _MAX_HEAP_TAG{ int* HEAP; int heapSize; // 堆中数据的实际大小 int heapLen; // 堆数组的长度 }MAX_HEAP;

MAX_HEAP* create_heap(int len){ MAX_HEAP* newHeap = new MAX_HEAP; newHeap->heapLen = len; newHeap->heapSize = 0; newHeap->HEAP = new int[len];

return newHeap;

http://www.lisdn.com

http://www.lisdn.com

}

void delete_heap(MAX_HEAP* heap){ delete[] heap->HEAP; delete heap; }

inline int heap_size(MAX_HEAP* heap){ return heap->heapSize; } inline int heap_length(MAX_HEAP* heap){ return heap->heapLen; }

void max_heapify(MAX_HEAP* heap, int i){

int *A= heap->HEAP; int cur = A[i]; int max = i;

if( (2*i 1) < heap->heapSize && A[2*i 1] > cur ) max = 2*i 1; if( (2*i 2) < heap->heapSize && A[2*i 2] > A[max] ) max = 2*i 2;

http://www.lisdn.com

http://www.lisdn.com

if( i == max) return; else{ A[i] = A[max]; A[max] = cur; max_heapify(heap, max); } }

void build_max_heap(MAX_HEAP* heap){ for( int i = heap_size(heap)/2-1 ; i>=0; i --) max_heapify(heap, i); }

void _heap_sort(MAX_HEAP* heap){ build_max_heap(heap); for( int i = heap->heapSize; i > 1; i --){ int tmp = heap->HEAP[0]; heap->HEAP[0] = heap->HEAP[heap->heapSize-1]; heap->HEAP[heap->heapSize-1] = tmp; heap->heapSize --; max_heapify(heap, 0); } }

void heap_sort(int a[], int len){

http://www.lisdn.com

http://www.lisdn.com

MAX_HEAP* heap = new MAX_HEAP; heap->HEAP = a; heap->heapLen = heap->heapSize = len; _heap_sort(heap); delete heap; } // // 堆排序 //////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////// // 快速排序 //

int partition(int A[], int p, int r){ int i, x, j,tmp; i = p - 1; x = A[r]; for( j = p; j <= r - 1; j ){ if( A[j] <= x ){ i; tmp = A[j]; A[j] = A[i]; A[i] = tmp; }

http://www.lisdn.com

http://www.lisdn.com

}

A[r] = A[i 1]; A[i 1] = x;

return (i 1); }

void _iquick_sort(int A[], int p, int r){ if( p < r){ int q = partition(A, p, r); _iquick_sort(A, p, q - 1); _iquick_sort(A, q 1, r); } }

void quick_sort(int A[], int len){ _iquick_sort(A, 0, len - 1); } // // 快速排序 ////////////////////////////////////////////////////////////////////////// 网友回复:就来看看 学习学习 网友回复:. 网友回复:mark！

http://www.lisdn.com

http://www.lisdn.com

C/C code

http://www.lisdn.com

http://www.lisdn.com

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/

#include<iostream>

#include<vector>

using namespace std;

int _sum(vector<int>& a, int& low, int& high){

int conSum=0;

for(int i=low; i<=high; i ){

http://www.lisdn.com

http://www.lisdn.com

conSum =a[i];

}

return conSum;

}

int maxContiguous1(vector<int>& a, int& low, int& high) {//O(N^3)

int maxSum = 0;

int sum=0;

int _high=0;

for (int i = 0; i < high ; i ) {

for (int j = i

1; j < high; j ) {

if (_sum(a,i,j)> maxSum) {

maxSum = _sum(a,i,j);

http://www.lisdn.com

http://www.lisdn.com

low = i;

_high = j;

}

}

}

high=_high;

return maxSum;

}

int maxContiguous2(vector<int>& a, int& low, int& high) {//O(N^2)

int maxSum = 0;

int sum=0;

http://www.lisdn.com

http://www.lisdn.com

int _high=0;

for (int i = 0; i < high ; i ) {

sum=a[i];

for (int j = i

1; j < high; j ) {

sum =a[j];

if (sum> maxSum) {

maxSum = sum;

low = i;

_high = j;

}

}

}

high=_high;

http://www.lisdn.com

http://www.lisdn.com

return maxSum;

}

int maxContiguous3(vector<int>& a, int& low, int& high){//O(N)

int maxSum = 0;

int sum=0;

int _high=0;

for (int j=0,i = 0; i < high ; i ) {

sum =a[i];

if (sum> maxSum) {

maxSum = sum;

low =j;

http://www.lisdn.com

http://www.lisdn.com

_high = i;

}

else if(sum<0){

j=i 1;

sum=0;

}

}

high=_high;

return maxSum;

}

int main() {

int b[] = {6, 1, -9, 4, -3, 2, 8, -7, 5, 0};

http://www.lisdn.com

http://www.lisdn.com

vector<int> a(b, b

10);

int low = 0, high = a.size()-1;

int maxSum = maxContiguous3(a, low, high);

cout << "from a[" << low << "] to a[" << high << "] =" << maxSum;

system("pause");

}

http://www.lisdn.com

http://www.lisdn.com

【算法 5.1】 计算属性集Ｘ关于Ｆ的闭包Ｘ＋。 输入：属性集Ｘ为Ｕ的子集，函数依赖集Ｆ。 输出：Ｘ＋。 步骤： (1) 置初始值 A=ф，A*=X； (2) 如果 A≠A*，置 A=A*，否则转(4)； (3) 依次检查 F 中的每一个函数依赖 Y→Z，若 Y?A*，置 A*=A*∪Z。全部搜索完,转(2)； (4) 输出 A*，即为 X 。

【例】 (AB) 。

http://www.lisdn.com

http://www.lisdn.com

(3) 第二次扫描 F，找到 C→E 和 AC→B，其左部?ABCD，故置 A*=ABCDE。搜索完,转(2)； (2) 因 A≠A*，置 A=ABCDE； (3) 第三次扫描 F，找到 EC→B，其左部?ABCDE，故置 A*=ABCDE。搜索完,转(2)； (2) 因 A=A*，转(4)； (4) 输出 A*，即(AB) =ABCDE。

http://www.lisdn.com

http://www.lisdn.com

} else { if( *( a e ) < tmp ) { *( a i ) = *( a e ); i = e; } --e; } } *( a i ) = tmp; return i; } void PartitionSort( int* a, int start, int end ) //QuickSort { if( start >= end ) return; int i = Partition( a, start, end ); PartitionSort( a, start, i - 1 ); PartitionSort( a, i 1, end ); }

void Heapify( vector <int>& vec ) { int size = vec.size();

http://www.lisdn.com

http://www.lisdn.com

for( int i = 1; i < size; i ) { int cur = i; while( cur > 0 ) { int p = ( cur - 1 ) / 2; if( vec[ cur ] > vec[ p ] ) { int tmp = vec[ cur ]; vec[ cur ] = vec[ p ]; vec[ p ] = tmp; cur = p; } else break; } } }

void Filter( vector <int>& vec, int end ) { int i = 0; while( i <= end / 2 ) { int lc = 2 * i 1;

http://www.lisdn.com

http://www.lisdn.com

int rc = 2 * i 2; int index = vec[ lc ] > vec[ rc ] ? lc : rc; if( index <= end && vec[ index ] > vec[ i ] ) { int tmp = vec[ index ]; vec[ index ] = vec[ i ]; vec[ i ] = tmp; i = index; continue; } else { if( lc <= end && vec[ lc ] > vec[ i ] ) { int tmp = vec[ lc ]; vec[ lc ] = vec[ i ]; vec[ i ] = tmp; i = lc; continue; } } break; } }

http://www.lisdn.com

http://www.lisdn.com

void HeapSort( vector <int>& vec ) { Heapify( vec ); copy( vec.begin(), vec.end(), ostream_iterator <int>( cout, " " ) ); for( int i = vec.size() - 1; i > 0; --i ) { int tmp = vec[ 0 ]; vec[ 0 ] = vec[ i ]; vec[ i ] = tmp; Filter( vec, i - 1 ); } }

void Merge( vector <int>& vec, int b, int m, int e ) { int i = m; while( b < m && i <= e ) { if( vec[ b ] > vec[ i ] ) { int tmp = vec[ i ]; for( int k = i - 1; k >= b; --k ) { vec[ k 1 ] = vec[ k ]; }

http://www.lisdn.com

http://www.lisdn.com

vec[ b ] = tmp; m; b; i; } else { b; } } } void MergeSort( vector <int>& vec, int b, int e ) { if( b == e ) return; int i = ( b e ) / 2; MergeSort( vec, b, i ); MergeSort( vec, i 1, e ); Merge( vec, b, i 1, e ); } linux linux 系统 linux 教程 linux 软件开发

http://www.lisdn.com

C语言经典算法100例
C语言经典算法100例_电子/电路_工程科技_专业资料。【程序 1】 题目:有 1、...1.程序分析:(a>b)?a:b 这是条件运算符的基本例子。 2.程序源代码: main...
C语言经典算法50例
C语言经典算法50例_IT/计算机_专业资料。C/C++语言经典实用、趣味程序设计编程...在屏幕上用“*”显示 0~360 度的余弦函数 cos(x)曲线 *问题分析与算法设计...

C语言100个经典算法
C语言100个经典算法_计算机软件及应用_IT/计算机_专业资料。C语言100个经典算法...程序分析:先把图形分成两部分来看待,前四行一个规律,后三行一个规律,利 用...
100例C语言经典算法
100例C语言经典算法_计算机软件及应用_IT/计算机_专业资料。经典算法 程序分析:兔子的规律为数列 1,1,2,3,5,8,13,21…. ___ 程序源代码: main() { long...
C语言经典算法100例
C 语言经典算法 100 例(1)(2007-08-15 15:09:22) C 语言编程经典 100 ...1.程序分析:(a〉b)?a:b 这是条件运算符的基本例子。 2.程序源代码: main...
C语言经典算法100例
C语言经典算法100例_电子/电路_工程科技_专业资料。文章由剑舞冲天精心整理,...1.程序分析:在 10 万以内判断,先将该数加上 100 后再开方,再将该数加上 ...
c语言经典算法
c语言经典算法_电脑基础知识_IT/计算机_专业资料。目 录 第一章 数值处理 .....如 键盘上输入: 5-9.0/3+8/4*2= 则屏幕上输出: 7.000000 算法分析:...

C语言经典算法系列 14页 2财富值 C语言经典算法详解 18页 免费 C语言100个经典算法 27页 免费 C语言经典一百算法 9页 2财富值喜欢此文档的还喜欢 ...