常用演算法c
經典C源程序100例
【程序1】
題目：有1、2、3、4個數字，能組成多少個互不相同且無重復數字的三位數？都是多少？
1.程序分析：可填在百位、十位、個位的數字都是1、2、3、4。組成所有的排列後再去
掉不滿足條件的排列。
2.程序源代碼：
main()
{
int i,j,k;
printf("\n");
for(i=1;i<5;i++) ／*以下為三重循環*/
for(j=1;j<5;j++)
for (k=1;k<5;k++)
{
if (i!=k&&i!=j&&j!=k) /*確保i、j、k三位互不相同*/
printf("%d,%d,%d\n",i,j,k);
}
}
==============================================================
【程序2】
題目：企業發放的獎金根據利潤提成。利潤(I)低於或等於10萬元時，獎金可提10%；利潤高
於10萬元，低於20萬元時，低於10萬元的部分按10%提成，高於10萬元的部分，可可提
成7.5%；20萬到40萬之間時，高於20萬元的部分，可提成5%；40萬到60萬之間時高於
40萬元的部分，可提成3%；60萬到100萬之間時，高於60萬元的部分，可提成1.5%，高於
100萬元時，超過100萬元的部分按1%提成，從鍵盤輸入當月利潤I，求應發放獎金總數？
1.程序分析：請利用數軸來分界，定位。注意定義時需把獎金定義成長整型。
2.程序源代碼：
main()
{
long int i;
int bonus1,bonus2,bonus4,bonus6,bonus10,bonus;
scanf("%ld",&i);
bonus1=100000*0.1;bonus2=bonus1+100000*0.75;
bonus4=bonus2+200000*0.5;
bonus6=bonus4+200000*0.3;
bonus10=bonus6+400000*0.15;
if(i<=100000)
bonus=i*0.1;
else if(i<=200000)
bonus=bonus1+(i-100000)*0.075;
else if(i<=400000)
bonus=bonus2+(i-200000)*0.05;
else if(i<=600000)
bonus=bonus4+(i-400000)*0.03;
else if(i<=1000000)
bonus=bonus6+(i-600000)*0.015;
else
bonus=bonus10+(i-1000000)*0.01;
printf("bonus=%d",bonus);
}
==============================================================
【程序3】
題目：一個整數，它加上100後是一個完全平方數，再加上168又是一個完全平方數，請問該數是多少？
1.程序分析：在10萬以內判斷，先將該數加上100後再開方，再將該數加上268後再開方，如果開方後
的結果滿足如下條件，即是結果。請看具體分析：
2.程序源代碼：
#include "math.h"
main()
{
long int i,x,y,z;
for (i=1;i<100000;i++)
{ x=sqrt(i+100); /*x為加上100後開方後的結果*/
y=sqrt(i+268); /*y為再加上168後開方後的結果*/
if(x*x==i+100&&y*y==i+268)/*如果一個數的平方根的平方等於該數，這說明此數是完全平方數*/
printf("\n%ld\n",i);
}
}
==============================================================
【程序4】
題目：輸入某年某月某日，判斷這一天是這一年的第幾天？
1.程序分析：以3月5日為例，應該先把前兩個月的加起來，然後再加上5天即本年的第幾天，特殊
情況，閏年且輸入月份大於3時需考慮多加一天。
2.程序源代碼：
main()
{
int day,month,year,sum,leap;
printf("\nplease input year,month,day\n");
scanf("%d,%d,%d",&year,&month,&day);
switch(month)/*先計算某月以前月份的總天數*/
{
case 1:sum=0;break;
case 2:sum=31;break;
case 3:sum=59;break;
case 4:sum=90;break;
case 5:sum=120;break;
case 6:sum=151;break;
case 7:sum=181;break;
case 8:sum=212;break;
case 9:sum=243;break;
作者： zhlei81 2005-1-22 11:29 回復此發言
--------------------------------------------------------------------------------
2 經典C源程序100例
case 10:sum=273;break;
case 11:sum=304;break;
case 12:sum=334;break;
default:printf("data error");break;
}
sum=sum+day; /*再加上某天的天數*/
if(year%400==0||(year%4==0&&year%100!=0))/*判斷是不是閏年*/
leap=1;
else
leap=0;
if(leap==1&&month>2)/*如果是閏年且月份大於2,總天數應該加一天*/
sum++;
printf("It is the %dth day.",sum);}
==============================================================
【程序5】
題目：輸入三個整數x,y,z，請把這三個數由小到大輸出。
1.程序分析：我們想辦法把最小的數放到x上，先將x與y進行比較，如果x>y則將x與y的值進行交換，
然後再用x與z進行比較，如果x>z則將x與z的值進行交換，這樣能使x最小。
2.程序源代碼：
main()
{
int x,y,z,t;
scanf("%d%d%d",&x,&y,&z);
if (x>y)
{t=x;x=y;y=t;} /*交換x,y的值*/
if(x>z)
{t=z;z=x;x=t;}/*交換x,z的值*/
if(y>z)
{t=y;y=z;z=t;}/*交換z,y的值*/
printf("small to big: %d %d %d\n",x,y,z);
}
==============================================================
【程序6】
題目：用*號輸出字母C的圖案。
1.程序分析：可先用'*'號在紙上寫出字母C，再分行輸出。
2.程序源代碼：
#include "stdio.h"
main()
{
printf("Hello C-world!\n");
printf(" ****\n");
printf(" *\n");
printf(" * \n");
printf(" ****\n");
}
==============================================================
【程序7】
題目：輸出特殊圖案，請在c環境中運行，看一看，Very Beautiful!
1.程序分析：字元共有256個。不同字元，圖形不一樣。
2.程序源代碼：
#include "stdio.h"
main()
{
char a=176,b=219;
printf("%c%c%c%c%c\n",b,a,a,a,b);
printf("%c%c%c%c%c\n",a,b,a,b,a);
printf("%c%c%c%c%c\n",a,a,b,a,a);
printf("%c%c%c%c%c\n",a,b,a,b,a);
printf("%c%c%c%c%c\n",b,a,a,a,b);}
==============================================================
【程序8】
題目：輸出9*9口訣。
1.程序分析：分行與列考慮，共9行9列，i控制行，j控制列。
2.程序源代碼：
#include "stdio.h"
main()
{
int i,j,result;
printf("\n");
for (i=1;i<10;i++)
{ for(j=1;j<10;j++)
{
result=i*j;
printf("%d*%d=%-3d",i,j,result);/*-3d表示左對齊，佔3位*/
}
printf("\n");/*每一行後換行*/
}
}
==============================================================
【程序9】
題目：要求輸出國際象棋棋盤。
1.程序分析：用i控制行，j來控制列，根據i+j的和的變化來控制輸出黑方格，還是白方格。
2.程序源代碼：
#include "stdio.h"
main()
{
int i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
if((i+j)%2==0)
printf("%c%c",219,219);
else
printf(" ");
printf("\n");
}
}
==============================================================
【程序10】
題目：列印樓梯，同時在樓梯上方列印兩個笑臉。
1.程序分析：用i控制行，j來控制列，j根據i的變化來控制輸出黑方格的個數。
2.程序源代碼：
#include "stdio.h"
main()
{
int i,j;
printf("\1\1\n");/*輸出兩個笑臉*/
for(i=1;i<11;i++)
{
for(j=1;j<=i;j++)
printf("%c%c",219,219);
printf("\n");
}
}
作者： zhlei81 2005-1-22 11:29 回復此發言
--------------------------------------------------------------------------------
3 回復：經典C源程序100例
【程序11】
題目：古典問題：有一對兔子，從出生後第3個月起每個月都生一對兔子，小兔子長到第三個月
後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？
1.程序分析： 兔子的規律為數列1,1,2,3,5,8,13,21....
2.程序源代碼：
main()
{
long f1,f2;
int i;
f1=f2=1;
for(i=1;i<=20;i++)
{ printf("%12ld %12ld",f1,f2);
if(i%2==0) printf("\n");/*控制輸出，每行四個*/
f1=f1+f2; /*前兩個月加起來賦值給第三個月*/
f2=f1+f2; /*前兩個月加起來賦值給第三個月*/
}
}
==============================================================
【程序12】
題目：判斷101-200之間有多少個素數，並輸出所有素數。
1.程序分析：判斷素數的方法：用一個數分別去除2到sqrt(這個數)，如果能被整除，
則表明此數不是素數，反之是素數。
2.程序源代碼：
#include "math.h"
main()
{
int m,i,k,h=0,leap=1;
printf("\n");
for(m=101;m<=200;m++)
{ k=sqrt(m+1);
for(i=2;i<=k;i++)
if(m%i==0)
{leap=0;break;}
if(leap) {printf("%-4d",m);h++;
if(h%10==0)
printf("\n");
}
leap=1;
}
printf("\nThe total is %d",h);
}
==============================================================
【程序13】
題目：列印出所有的「水仙花數」，所謂「水仙花數」是指一個三位數，其各位數字立方和等於該數
本身。例如：153是一個「水仙花數」，因為153=1的三次方＋5的三次方＋3的三次方。
1.程序分析：利用for循環控制100-999個數，每個數分解出個位，十位，百位。
2.程序源代碼：
main()
{
int i,j,k,n;
printf("'water flower'number is:");
for(n=100;n<1000;n++)
{
i=n/100;/*分解出百位*/
j=n/10%10;/*分解出十位*/
k=n%10;/*分解出個位*/
if(i*100+j*10+k==i*i*i+j*j*j+k*k*k)
{
printf("%-5d",n);
}
}
printf("\n");
}
==============================================================
【程序14】
題目：將一個正整數分解質因數。例如：輸入90,列印出90=2*3*3*5。
程序分析：對n進行分解質因數，應先找到一個最小的質數k，然後按下述步驟完成：
(1)如果這個質數恰等於n，則說明分解質因數的過程已經結束，列印出即可。
(2)如果n<>k，但n能被k整除，則應列印出k的值，並用n除以k的商,作為新的正整數你n,
重復執行第一步。
(3)如果n不能被k整除，則用k+1作為k的值,重復執行第一步。
2.程序源代碼：
/* zheng int is divided yinshu*/
main()
{
int n,i;
printf("\nplease input a number:\n");
scanf("%d",&n);
printf("%d=",n);
for(i=2;i<=n;i++)
{
while(n!=i)
{
if(n%i==0)
{ printf("%d*",i);
n=n/i;
}
else
break;
}
}
printf("%d",n);}
==============================================================
【程序15】
題目：利用條件運算符的嵌套來完成此題：學習成績>=90分的同學用A表示，60-89分之間的用B表示，
60分以下的用C表示。
1.程序分析：(a>b)?a:b這是條件運算符的基本例子。
2.程序源代碼：
main()
{
int score;
char grade;
printf("please input a score\n");
scanf("%d",&score);
grade=score>=90?'A':(score>=60?'B':'C');
printf("%d belongs to %c",score,grade);
}
==============================================================
【程序16】
題目：輸入兩個正整數m和n，求其最大公約數和最小公倍數。
作者： zhlei81 2005-1-22 11:30 回復此發言
--------------------------------------------------------------------------------
4 回復：經典C源程序100例
1.程序分析：利用輾除法。
2.程序源代碼：
main()
{
int a,b,num1,num2,temp;
printf("please input two numbers:\n");
scanf("%d,%d",&num1,&num2);
if(num1 { temp=num1;
num1=num2;
num2=temp;
}
a=num1;b=num2;
while(b!=0)/*利用輾除法，直到b為0為止*/
{
temp=a%b;
a=b;
b=temp;
}
printf("gongyueshu:%d\n",a);
printf("gongbeishu:%d\n",num1*num2/a);
}
==============================================================
【程序17】
題目：輸入一行字元，分別統計出其中英文字母、空格、數字和其它字元的個數。
1.程序分析：利用while語句,條件為輸入的字元不為'\n'.
2.程序源代碼：
#include "stdio.h"
main()
{char c;
int letters=0,space=0,digit=0,others=0;
printf("please input some characters\n");
while((c=getchar())!='\n')
{
if(c>='a'&&c<='z'||c>='A'&&c<='Z')
letters++;
else if(c==' ')
space++;
else if(c>='0'&&c<='9')
digit++;
else
others++;
}
printf("all in all:char=%d space=%d digit=%d others=%d\n",letters,
space,digit,others);
}
==============================================================
【程序18】
題目：求s=a+aa+aaa+aaaa+aa...a的值，其中a是一個數字。例如2+22+222+2222+22222(此時
共有5個數相加)，幾個數相加有鍵盤控制。
1.程序分析：關鍵是計算出每一項的值。
2.程序源代碼：
main()
{
int a,n,count=1;
long int sn=0,tn=0;
printf("please input a and n\n");
scanf("%d,%d",&a,&n);
printf("a=%d,n=%d\n",a,n);
while(count<=n)
{
tn=tn+a;
sn=sn+tn;
a=a*10;
++count;
}
printf("a+aa+...=%ld\n",sn);
}
==============================================================
【程序19】
題目：一個數如果恰好等於它的因子之和，這個數就稱為「完數」。例如6=1＋2＋3.編程
找出1000以內的所有完數。
1. 程序分析：請參照程序<--上頁程序14.
2.程序源代碼：
main()
{
static int k[10];
int i,j,n,s;
for(j=2;j<1000;j++)
{
n=-1;
s=j;
for(i=1;i {
if((j%i)==0)
{ n++;
s=s-i;
k[n]=i;
}
}
if(s==0)
{
printf("%d is a wanshu",j);
for(i=0;i printf("%d,",k[i]);
printf("%d\n",k[n]);
}
}
}
==============================================================
【程序20】
題目：一球從100米高度自由落下，每次落地後反跳回原高度的一半；再落下，求它在
第10次落地時，共經過多少米？第10次反彈多高？
1.程序分析：見下面注釋
2.程序源代碼：
main()
{
float sn=100.0,hn=sn/2;
int n;
for(n=2;n<=10;n++)
{
sn=sn+2*hn;/*第n次落地時共經過的米數*/
hn=hn/2; /*第n次反跳高度*/
}
printf("the total of road is %f\n",sn);
printf("the tenth is %f meter\n",hn);
}
作者： zhlei81 2005-1-22 11:30 回復此發言
--------------------------------------------------------------------------------
B. C語言經典演算法：如何較快的分解質因數
將一個正整數分解質因數。例如：輸入90,列印出90=2*3*3*5。初級演算法：#include
#include
#include
int
main()
{
int
n,i;
scanf("%d",&n);
printf("%d=",n);
for(i=2;i
C. c語言（高分）
1.相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數：f(n)=n*f(n-1)
在f(3)的運算過程中,遞歸的數據流動過程如下:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而遞推如下:
f(0)-->f(1)-->f(2)-->f(3)
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.
2.所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
3.索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位
置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。
4.插入法排序
#define N 10
#include"stdio.h"
main()
{ int i,j,k,t,a[N];
clrscr();
printf("Please input %d numbers:\n",N);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=1;i<N;i++)
{
for(j=0;j<i;j++)
{if(a[j]>a[i])
{t=a[i];
for(k=i;k>=j;k--)
a[k]=a[k-1];
a[j]=t;
}
}
}
printf("small to big order:\n");
for(i=0;i<N;i++)
printf("%-2d",a[i]);
printf("\n");
getch();
}
D. c語言三種排序
常用的c語言排序演算法主要有三種即冒泡法排序、選擇法排序、插入法排序。
一、冒泡排序冒泡排序：
是從第一個數開始，依次往後比較，在滿足判斷條件下進行交換。代碼實現（以降序排序為例）
#include<stdio.h>
int main()
{
int array[10] = { 6,9,7,8,5,3,4,0,1,2 };
int temp;
for (int i = 0; i < 10; i++)
{//循環次數
for (int j = 0; j <10 - i-1; j++)
{
if (array[j] < array[j+1])
{//前面一個數比後面的數大時發生交換 temp = array[j];
array[j] = array[j+1];
array[j + 1] = temp;
}
}
} //列印數組 for (int i = 0; i < 10; i++) printf("%2d", array[i]); return 0;}}
二、選擇排序以升序排序為例：
就是在指定下標的數組元素往後（指定下標的元素往往是從第一個元素開始，然後依次往後），找出除指定下標元素外的值與指定元素進行對比，滿足條件就進行交換。與冒泡排序的區別可以理解為冒泡排序是相鄰的兩個值對比，而選擇排序是遍歷數組，找出數組元素與指定的數組元素進行對比。（以升序為例）
#include<stdio.h>
int main()
{
int array[10] = { 6,9,7,8,5,3,4,0,1,2 };
int temp, index;
for (int i = 0; i < 9; i++) {
index = i;
for (int j = i; j < 10; j++)
{
if (array[j] < array[index])
index = j;
}
if(i != index)
{
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for(int i=0;i<10:i++)
printf("%2d"array[i]）
return 0；
}
三、快速排序
是通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
void QuickSort(int* arr, int size)
{
int temp, i, j;
for(i = 1; i <size; i++)
for(j=i; j>0; j--)
{
if(arr[j] <arr[j-1])
{
temp = arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
}
E. C語言演算法有哪些 並舉例和分析
演算法大全（C，C++）
一、 數論演算法
1．求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
2．求兩數的最小公倍數
function lcm(a,b:integer):integer;
begin
if a<b then swap(a,b);
lcm:=a;
while lcm mod b>0 do inc(lcm,a);
end;
3．素數的求法
A.小范圍內判斷一個數是否為質數：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then begin
prime:=false; exit;
end;
prime:=true;
end;
B.判斷longint范圍內的數是否為素數（包含求50000以內的素數表）：
procere getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i<50000 do begin
if p[i] then begin
j:=i*2;
while j<50000 do begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p[i] then begin
inc(l);pr[l]:=i;
end;
end;{getprime}
function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr[i]>=x then break
else if x mod pr[i]=0 then exit;
prime:=true;
end;{prime}
二、圖論演算法
1．最小生成樹
A.Prim演算法：
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{尋找離生成樹最近的未加入頂點k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {將頂點k加入生成樹}
{生成樹中增加一條新的邊k到closest[k]}
{修正各點的lowcost和closest值}
for j:=1 to n do
if cost[k,j]<lwocost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}
B.Kruskal演算法：(貪心)
按權值遞增順序刪去圖中的邊，若不形成迴路則將此邊加入最小生成樹。
function find(v:integer):integer; {返回頂點v所在的集合}
var i:integer;
begin
i:=1;
while (i<=n) and (not v in vset[i]) do inc(i);
if i<=n then find:=i else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset[i]:=[i];{初始化定義n個集合，第I個集合包含一個元素I}
p:=n-1; q:=1; tot:=0; {p為尚待加入的邊數，q為邊集指針}
sort;
{對所有邊按權值遞增排序，存於e[I]中，e[I].v1與e[I].v2為邊I所連接的兩個頂點的序號，e[I].len為第I條邊的長度}
while p>0 do begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i<>j then begin
inc(tot,e[q].len);
vset[i]:=vset[i]+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
2.最短路徑
A.標號法求解單源點最短路徑：
var
a:array[1..maxn,1..maxn] of integer;
b:array[1..maxn] of integer; {b[i]指頂點i到源點的最短路徑}
mark:array[1..maxn] of boolean;
procere bhf;
var
best,best_j:integer;
begin
fillchar(mark,sizeof(mark),false);
mark[1]:=true; b[1]:=0;{1為源點}
repeat
best:=0;
for i:=1 to n do
If mark[i] then {對每一個已計算出最短路徑的點}
for j:=1 to n do
if (not mark[j]) and (a[i,j]>0) then
if (best=0) or (b[i]+a[i,j]<best) then begin
best:=b[i]+a[i,j]; best_j:=j;
end;
if best>0 then begin
b[best_j]:=best；mark[best_j]:=true;
end;
until best=0;
end;{bhf}
B.Floyed演算法求解所有頂點對之間的最短路徑：
procere floyed;
begin
for I:=1 to n do
for j:=1 to n do
if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路徑上j的前驅結點}
for k:=1 to n do {枚舉中間結點}
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]<a[i,j] then begin
a[i,j]:=a[i,k]+a[k,j];
p[I,j]:=p[k,j];
end;
end;
C. Dijkstra 演算法：
var
a:array[1..maxn,1..maxn] of integer;
b,pre:array[1..maxn] of integer; {pre[i]指最短路徑上I的前驅結點}
mark:array[1..maxn] of boolean;
procere dijkstra(v0:integer);
begin
fillchar(mark,sizeof(mark),false);
for i:=1 to n do begin
d[i]:=a[v0,i];
if d[i]<>0 then pre[i]:=v0 else pre[i]:=0;
end;
mark[v0]:=true;
repeat {每循環一次加入一個離1集合最近的結點並調整其他結點的參數}
min:=maxint; u:=0; {u記錄離1集合最近的結點}
for i:=1 to n do
if (not mark[i]) and (d[i]<min) then begin
u:=i; min:=d[i];
end;
if u<>0 then begin
mark[u]:=true;
for i:=1 to n do
if (not mark[i]) and (a[u,i]+d[u]<d[i]) then begin
d[i]:=a[u,i]+d[u];
pre[i]:=u;
end;
end;
until u=0;
end;
3.計算圖的傳遞閉包
Procere Longlink;
Var
T:array[1..maxn,1..maxn] of boolean;
Begin
Fillchar(t,sizeof(t),false);
For k:=1 to n do
For I:=1 to n do
For j:=1 to n do T[I,j]:=t[I,j] or (t[I,k] and t[k,j]);
End;
4．無向圖的連通分量
A.深度優先
procere dfs ( now,color: integer);
begin
for i:=1 to n do
if a[now,i] and c[i]=0 then begin {對結點I染色}
c[i]:=color;
dfs(I,color);
end;
end;
B 寬度優先（種子染色法）
5．關鍵路徑
幾個定義： 頂點1為源點，n為匯點。
a. 頂點事件最早發生時間Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b. 頂點事件最晚發生時間 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c. 邊活動最早開始時間 Ee[I], 若邊I由<j,k>表示，則Ee[I] = Ve[j];
d. 邊活動最晚開始時間 El[I], 若邊I由<j,k>表示，則El[I] = Vl[k] – w[j,k];
若 Ee[j] = El[j] ，則活動j為關鍵活動，由關鍵活動組成的路徑為關鍵路徑。
求解方法：
a. 從源點起topsort,判斷是否有迴路並計算Ve;
b. 從匯點起topsort,求Vl;
c. 算Ee 和 El;
6．拓撲排序
找入度為0的點，刪去與其相連的所有邊，不斷重復這一過程。
例 尋找一數列，其中任意連續p項之和為正，任意q 項之和為負，若不存在則輸出NO.
7.迴路問題
Euler迴路(DFS)
定義：經過圖的每條邊僅一次的迴路。（充要條件：圖連同且無奇點）
Hamilton迴路
定義：經過圖的每個頂點僅一次的迴路。
一筆畫
充要條件：圖連通且奇點個數為0個或2個。
9．判斷圖中是否有負權迴路 Bellman-ford 演算法
x[I],y[I],t[I]分別表示第I條邊的起點，終點和權。共n個結點和m條邊。
procere bellman-ford
begin
for I:=0 to n-1 do d[I]:=+infinitive;
d[0]:=0;
for I:=1 to n-1 do
for j:=1 to m do {枚舉每一條邊}
if d[x[j]]+t[j]<d[y[j]] then d[y[j]]:=d[x[j]]+t[j];
for I:=1 to m do
if d[x[j]]+t[j]<d[y[j]] then return false else return true;
end;
10．第n最短路徑問題
*第二最短路徑：每舉最短路徑上的每條邊，每次刪除一條，然後求新圖的最短路徑，取這些路徑中最短的一條即為第二最短路徑。
*同理，第n最短路徑可在求解第n-1最短路徑的基礎上求解。
三、背包問題
*部分背包問題可有貪心法求解：計算Pi/Wi
數據結構：
w[i]:第i個背包的重量；
p[i]:第i個背包的價值；
1．0-1背包： 每個背包只能使用一次或有限次(可轉化為一次)：
A.求最多可放入的重量。
NOIP2001 裝箱問題
有一個箱子容量為v(正整數，o≤v≤20000)，同時有n個物品(o≤n≤30)，每個物品有一個體積 (正整數)。要求從 n 個物品中，任取若千個裝入箱內，使箱子的剩餘空間為最小。
l 搜索方法
procere search(k,v:integer); {搜索第k個物品，剩餘空間為v}
var i,j:integer;
begin
if v<best then best:=v;
if v-(s[n]-s[k-1])>=best then exit; {s[n]為前n個物品的重量和}
if k<=n then begin
if v>w[k] then search(k+1,v-w[k]);
search(k+1,v);
end;
end;
l DP
F[I,j]為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。
實現:將最優化問題轉化為判定性問題
f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 邊界：f[0,0]:=true.
For I:=1 to n do
For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];
優化：當前狀態只與前一階段狀態有關，可降至一維。
F[0]:=true;
For I:=1 to n do begin
F1:=f;
For j:=w[I] to v do
If f[j-w[I]] then f1[j]:=true;
F:=f1;
End;
B.求可以放入的最大價值。
F[I,j] 為容量為I時取前j個背包所能獲得的最大價值。
F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] }
C.求恰好裝滿的情況數。
DP:
Procere update;
var j,k:integer;
begin
c:=a;
for j:=0 to n do
if a[j]>0 then
if j+now<=n then inc(c[j+now],a[j]);
a:=c;
end;
2．可重復背包
A求最多可放入的重量。
F[I,j]為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。
狀態轉移方程為
f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])
B.求可以放入的最大價值。
USACO 1.2 Score Inflation
進行一次競賽，總時間T固定，有若干種可選擇的題目，每種題目可選入的數量不限，每種題目有一個ti（解答此題所需的時間）和一個si（解答此題所得的分數），現要選擇若干題目，使解這些題的總時間在T以內的前提下，所得的總分最大，求最大的得分。
*易想到：
f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j])
其中f[i,j]表示容量為i時取前j種背包所能達到的最大值。
*實現：
Begin
FillChar(f,SizeOf(f),0);
For i:=1 To M Do
For j:=1 To N Do
If i-problem[j].time>=0 Then
Begin
t:=problem[j].point+f[i-problem[j].time];
If t>f[i] Then f[i]:=t;
End;
Writeln(f[M]);
End.
C.求恰好裝滿的情況數。
Ahoi2001 Problem2
求自然數n本質不同的質數和的表達式的數目。
思路一，生成每個質數的系數的排列，在一一測試，這是通法。
procere try(dep:integer);
var i,j:integer;
begin
cal; {此過程計算當前系數的計算結果，now為結果}
if now>n then exit; {剪枝}
if dep=l+1 then begin {生成所有系數}
cal;
if now=n then inc(tot);
exit;
end;
for i:=0 to n div pr[dep] do begin
xs[dep]:=i;
try(dep+1);
xs[dep]:=0;
end;
end;
思路二，遞歸搜索效率較高
procere try(dep,rest:integer);
var i,j,x:integer;
begin
if (rest<=0) or (dep=l+1) then begin
if rest=0 then inc(tot);
exit;
end;
for i:=0 to rest div pr[dep] do
try(dep+1,rest-pr[dep]*i);
end;
{main: try(1,n); }
思路三：可使用動態規劃求解
USACO1.2 money system
V個物品，背包容量為n，求放法總數。
轉移方程：
Procere update;
var j,k:integer;
begin
c:=a;
for j:=0 to n do
if a[j]>0 then
for k:=1 to n div now do
if j+now*k<=n then inc(c[j+now*k],a[j]);
a:=c;
end;
{main}
begin
read(now); {讀入第一個物品的重量}
i:=0; {a[i]為背包容量為i時的放法總數}
while i<=n do begin
a[i]:=1; inc(i,now); end; {定義第一個物品重的整數倍的重量a值為1，作為初值}
for i:=2 to v do
begin
read(now);
update; {動態更新}
end;
writeln(a[n]);
四、排序演算法
A.快速排序：
procere qsort(l,r:integer);
var i,j,mid:integer;
begin
i:=l;j:=r; mid:=a[(l+r) div 2]; {將當前序列在中間位置的數定義為中間數}
repeat
while a[i]<mid do inc(i); {在左半部分尋找比中間數大的數}
while a[j]>mid do dec(j);{在右半部分尋找比中間數小的數}
if i<=j then begin {若找到一組與排序目標不一致的數對則交換它們}
swap(a[i],a[j]);
inc(i);dec(j); {繼續找}
end;
until i>j;
if l<j then qsort(l,j); {若未到兩個數的邊界，則遞歸搜索左右區間}
if i<r then qsort(i,r);
end;{sort}
B.插入排序：
思路：當前a[1]..a[i-1]已排好序了，現要插入a[i]使a[1]..a[i]有序。
procere insert_sort;
var i,j:integer;
begin
for i:=2 to n do begin
a[0]:=a[i];
j:=i-1;
while a[0]<a[j] do begin
a[j+1]:=a[j];
j:=j-1;
end;
a[j+1]:=a[0];
end;
end;{inset_sort}
C.選擇排序：
procere sort;
var i,j,k:integer;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then swap(a[i],a[j]);
end;
D. 冒泡排序
procere bubble_sort;
var i,j,k:integer;
begin
for i:=1 to n-1 do
for j:=n downto i+1 do
if a[j]<a[j-1] then swap( a[j],a[j-1]); {每次比較相鄰元素的關系}
end;
E.堆排序：
procere sift(i,m:integer);{調整以i為根的子樹成為堆,m為結點總數}
var k:integer;
begin
a[0]:=a[i]; k:=2*i;{在完全二叉樹中結點i的左孩子為2*i,右孩子為2*i+1}
while k<=m do begin
if (k<m) and (a[k]<a[k+1]) then inc(k);{找出a[k]與a[k+1]中較大值}
if a[0]<a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end
else k:=m+1;
end;
a[i]:=a[0]; {將根放在合適的位置}
end;
procere heapsort;
var
j:integer;
begin
for j:=n div 2 downto 1 do sift(j,n);
for j:=n downto 2 do begin
swap(a[1],a[j]);
sift(1,j-1);
end;
F. c語言演算法有哪些
這里整理c語言常用演算法，主要有：
交換演算法
查找最小值演算法
冒泡排序
選擇排序
插入排序
shell排序 (希爾排序)
歸並排序
快速排序
二分查找演算法
查找重復演算法