c语言最长递增子序列
⑴ c语言排序
//总共给你整理了7种排序算法：希尔排序，链式基数排序，归并排序
//起泡排序，简单选择排序，树形选择排序，堆排序,先自己看看吧，
//看不懂可以再问身边的人或者查资料,既然可以上网，我相信你所在的地方信息流通方式应该还行,所有的程序全部在VC++6.0下编译通过
//希尔排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void ShellInsert(SqList &L,int dk)
{ // 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前后记录位置的增量是dk,而不是1;
// 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4
int i,j;
for(i=dk+1;i<=L.length;++i)
if LT(L.r[i].key,L.r[i-dk].key)
{ // 需将L.r[i]插入有序增量子表
L.r[0]=L.r[i]; // 暂存在L.r[0]
for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j]; // 记录后移，查找插入位置
L.r[j+dk]=L.r[0]; // 插入
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}
void print1(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
void ShellSort(SqList &L,int dlta[],int t)
{ // 按增量序列dlta[0..t-1]对顺序表L作希尔排序。算法10.5
int k;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]); // 一趟增量为dlta[k]的插入排序
printf("第%d趟排序结果: ",k+1);
print(L);
}
}
#define N 10
#define T 3
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList l;
int dt[T]={5,3,1}; // 增量序列数组
for(int i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序后: ");
print1(l);
}
/*****************************************************************/
//链式基数排序
typedef int InfoType; // 定义其它数据项的类型
typedef int KeyType; // 定义RedType类型的关键字为整型
struct RedType // 记录类型(同c10-1.h)
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项
};
typedef char KeysType; // 定义关键字类型为字符型
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
#define MAX_NUM_OF_KEY 8 // 关键字项数的最大值
#define RADIX 10 // 关键字基数，此时是十进制整数的基数
#define MAX_SPACE 1000
struct SLCell // 静态链表的结点类型
{
KeysType keys[MAX_NUM_OF_KEY]; // 关键字
InfoType otheritems; // 其它数据项
int next;
};
struct SLList // 静态链表类型
{
SLCell r[MAX_SPACE]; // 静态链表的可利用空间，r[0]为头结点
int keynum; // 记录的当前关键字个数
int recnum; // 静态链表的当前长度
};
typedef int ArrType[RADIX];
void InitList(SLList &L,RedType D[],int n)
{ // 初始化静态链表L（把数组D中的数据存于L中）
char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
int i,j,max=D[0].key; // max为关键字的最大值
for(i=1;i<n;i++)
if(max<D[i].key)
max=D[i].key;
L.keynum=int(ceil(log10(max)));
L.recnum=n;
for(i=1;i<=n;i++)
{
L.r[i].otheritems=D[i-1].otherinfo;
itoa(D[i-1].key,c,10); // 将10进制整型转化为字符型,存入c
for(j=strlen(c);j<L.keynum;j++) // 若c的长度<max的位数,在c前补'0'
{
strcpy(c1,"0");
strcat(c1,c);
strcpy(c,c1);
}
for(j=0;j<L.keynum;j++)
L.r[i].keys[j]=c[L.keynum-1-j];
}
}
int ord(char c)
{ // 返回k的映射(个位整数)
return c-'0';
}
void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 算法10.15
{ // 静态键表L的r域中记录已按(keys[0],…,keys[i-1])有序。本算法按
// 第i个关键字keys[i]建立RADIX个子表,使同一子表中记录的keys[i]相同。
// f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录
int j,p;
for(j=0;j<RADIX;++j)
f[j]=0; // 各子表初始化为空表
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys[i]); // ord将记录中第i个关键字映射到[0..RADIX-1]
if(!f[j])
f[j]=p;
else
r[e[j]].next=p;
e[j]=p; // 将p所指的结点插入第j个子表中
}
}
int succ(int i)
{ // 求后继函数
return ++i;
}
void Collect(SLCell r[],ArrType f,ArrType e)
{ // 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成
// 一个链表，e[0..RADIX-1]为各子表的尾指针。算法10.16
int j,t;
for(j=0;!f[j];j=succ(j)); // 找第一个非空子表，succ为求后继函数
r[0].next=f[j];
t=e[j]; // r[0].next指向第一个非空子表中第一个结点
while(j<RADIX-1)
{
for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); // 找下一个非空子表
if(f[j])
{ // 链接两个非空子表
r[t].next=f[j];
t=e[j];
}
}
r[t].next=0; // t指向最后一个非空子表中的最后一个结点
}
void printl(SLList L)
{ // 按链表输出静态链表
int i=L.r[0].next,j;
while(i)
{
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" ");
i=L.r[i].next;
}
}
void RadixSort(SLList &L)
{ // L是采用静态链表表示的顺序表。对L作基数排序，使得L成为按关键字
// 自小到大的有序静态链表，L.r[0]为头结点。算法10.17
int i;
ArrType f,e;
for(i=0;i<L.recnum;++i)
L.r[i].next=i+1;
L.r[L.recnum].next=0; // 将L改造为静态链表
for(i=0;i<L.keynum;++i)
{ // 按最低位优先依次对各关键字进行分配和收集
Distribute(L.r,i,f,e); // 第i趟分配
Collect(L.r,f,e); // 第i趟收集
printf("第%d趟收集后:\n",i+1);
printl(L);
printf("\n");
}
}
void print(SLList L)
{ // 按数组序号输出静态链表
int i,j;
printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
for(i=1;i<=L.recnum;i++)
{
printf("keys=");
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
}
}
void Sort(SLList L,int adr[]) // 改此句(类型)
{ // 求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号
int i=1,p=L.r[0].next;
while(p)
{
adr[i++]=p;
p=L.r[p].next;
}
}
void Rearrange(SLList &L,int adr[]) // 改此句(类型)
{ // adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。
// 本算法按adr重排L.r，使其有序。算法10.18(L的类型有变)
int i,j,k;
for(i=1;i<L.recnum;++i) // 改此句(类型)
if(adr[i]!=i)
{
j=i;
L.r[0]=L.r[i]; // 暂存记录L.r[i]
while(adr[j]!=i)
{ // 调整L.r[adr[j]]的记录到位直到adr[j]=i为止
k=adr[j];
L.r[j]=L.r[k];
adr[j]=j;
j=k; // 记录按序到位
}
L.r[j]=L.r[0];
adr[j]=j;
}
}
#define N 10
void main()
{
RedType d[N]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
SLList l;
int *adr;
InitList(l,d,N);
printf("排序前(next域还没赋值):\n");
print(l);
RadixSort(l);
printf("排序后(静态链表):\n");
print(l);
adr=(int*)malloc((l.recnum)*sizeof(int));
Sort(l,adr);
Rearrange(l,adr);
printf("排序后(重排记录):\n");
print(l);
}
/*******************************************/
//归并排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) // 将SR中记录由小到大地并入TR
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; // 将剩余的SR[i..m]复制到TR
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; // 将剩余的SR[j..n]复制到TR
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ // 将SR[s..t]归并排序为TR1[s..t]。算法10.13
int m;
RedType TR2[MAXSIZE+1];
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]
}
}
void MergeSort(SqList &L)
{ // 对顺序表L作归并排序。算法10.14
MSort(L.r,L.r,1,L.length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 7
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(l);
printf("排序后:\n");
print(l);
}
/**********************************************/
//起泡排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
#define N 8
void bubble_sort(int a[],int n)
{ // 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i>1&&change;--i)
{
change=FALSE;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=TRUE;
}
}
}
void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}
void main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序后:\n");
print(d,N);
}
/****************************************************/
//简单选择排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
int SelectMinKey(SqList L,int i)
{ // 返回在L.r[i..L.length]中key最小的记录的序号
KeyType min;
int j,k;
k=i; // 设第i个为最小
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) // 找到更小的
{
k=j;
min=L.r[j].key;
}
return k;
}
void SelectSort(SqList &L)
{ // 对顺序表L作简单选择排序。算法10.9
int i,j;
RedType t;
for(i=1;i<L.length;++i)
{ // 选择第i小的记录，并交换到位
j=SelectMinKey(L,i); // 在L.r[i..L.length]中选择key最小的记录
if(i!=j)
{ // 与第i个记录交换
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(l);
printf("排序后:\n");
print(l);
}
/************************************************/
//树形选择排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int InfoType; // 定义其它数据项的类型
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void TreeSort(SqList &L)
{ // 树形选择排序
int i,j,j1,k,k1,l,n=L.length;
RedType *t;
l=(int)ceil(log(n)/log(2))+1; // 完全二叉树的层数
k=(int)pow(2,l)-1; // l层完全二叉树的结点总数
k1=(int)pow(2,l-1)-1; // l-1层完全二叉树的结点总数
t=(RedType*)malloc(k*sizeof(RedType)); // 二叉树采用顺序存储结构
for(i=1;i<=n;i++) // 将L.r赋给叶子结点
t[k1+i-1]=L.r[i];
for(i=k1+n;i<k;i++) // 给多余的叶子的关键字赋无穷大
t[i].key=INT_MAX;
j1=k1;
j=k;
while(j1)
{ // 给非叶子结点赋值
for(i=j1;i<j;i+=2)
t[i].key<t[i+1].key?(t[(i+1)/2-1]=t[i]):(t[(i+1)/2-1]=t[i+1]);
j=j1;
j1=(j1-1)/2;
}
for(i=0;i<n;i++)
{
L.r[i+1]=t[0]; // 将当前最小值赋给L.r[i]
j1=0;
for(j=1;j<l;j++) // 沿树根找结点t[0]在叶子中的序号j1
t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
t[j1].key=INT_MAX;
while(j1)
{
j1=(j1+1)/2-1; // 序号为j1的结点的双亲结点序号
t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
}
}
free(t);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
TreeSort(l);
printf("排序后:\n");
print(l);
}
/****************************/
//堆排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
typedef SqList HeapType; // 堆采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m) // 算法10.10
{ // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数
// 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{ // 沿key较大的孩子结点向下筛选
if(j<m&<(H.r[j].key,H.r[j+1].key))
++j; // j为key较大的记录的下标
if(!LT(rc.key,H.r[j].key))
break; // rc应插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; // 插入
}
void HeapSort(HeapType &H)
{ // 对顺序表H进行堆排序。算法10.11
RedType t;
int i;
for(i=H.length/2;i>0;--i) // 把H.r[1..H.length]建成大顶堆
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{ // 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1); // 将H.r[1..i-1]重新调整为大顶堆
}
}
void print(HeapType H)
{
int i;
for(i=1;i<=H.length;i++)
printf("(%d,%d)",H.r[i].key,H.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
HeapType h;
int i;
for(i=0;i<N;i++)
h.r[i+1]=d[i];
h.length=N;
printf("排序前:\n");
print(h);
HeapSort(h);
printf("排序后:\n");
print(h);
}
⑵ C语言，最长上升子序列数,,
最长上升子序列（LIS）
问题描述：设现在有一串序列，要求找出它的一串子序列，这串子序列可以不连续，但必须满足它是严格的单调递増的且为最长的。把这个长度输出。
示例：1 7 3 5 9 4 8 结果为4
题例：参看POJ 2533
解法：
1. DP之O(n2)算法：先按DP的思想来分析一下，要想求n个数的最长上升子序列，设有数据数组data[n]和状态数组dp[n]，则对其尾元素data[n]来说，它的最长上升子序列就是它自己，即dp[n]=1，而当把它的前一个元素data[n-1]考虑进来时，如果data[n-1]<data[n]则会存在一个长度为2的上升子序列，如果data[n-1]>data[n]那么这个长度仍会是1。当把这个思想一般化的时候，对于任意一个元素data[k]来说，我们需要找出在data[k]以后的元素中比data[k]大，并且最长的一个序列做为它的后继。这样dp[k]就可以写成dp[k+1]+1。现在我们定义一个量dp[k]=m，它代表着到第k个元素为止（可以包含k也可以不包含k），它的最长上升序列的长度为m。仔细体会dp[k]=m的意义，这里面的k是可包括在内，也可以不包括在内的（与之前的最大子序列和不同）。要想确定这个m的值，就必须找到一个在第k个元素之前的一个元素的值小于data[k]的值，并且那个元素所对应的dp值是找到的满足第一个条件前提下dp值最大的一个。这就意味着我们需要内层遍历之前算出来的dp值，所以需要两层循环来实现这个算法。这样我们就可以总结出状态转移方程为dp[k]=max(dp[i](1<=i<=k&&a[i]<a[k])+1。其中找dp[i]的过程我们需要用一层循环来实现，而找dp[k]的过程也要一层循环，所以我们得到了O(n2)的算法。
dp[k]=max(dp[i])+1 其中i满足(1<=i<=k&&a[i]<a[k])
例程：
#include <stdio.h>
const int inf = -0x3fffffff;
int main(void)
{
int i,j,len,max,res,data[] = {1,7,3,5,9,4,8},dp[20]={1};
len = sizeof(data)/sizeof(int);
res = max = inf;
for(i=1;i<len;i++)
{
max = inf;
for(j=0;j<=i;j++)
if(data[i]>data[j]&&max<dp[j])
max=dp[j];
dp[i]=max+1;
if(res<dp[i])
res = dp[i];
}
printf("%d\n",res);
return 0;
}
⑶ C语言中基本的几种算法有哪些越多越好！就像打擂台算法'冒泡排序法等等...
排序算法
冒泡排序
选择排序
快速排序
高精度运算
存储方法
加法运算
减法运算
乘法运算
扩大进制数
习题与练习
搜索算法
枚举算法
深度优先搜索
广度优先搜索
8数码问题
n皇后问题
搜索算法习题
枚举法习题
聪明的打字员
量水问题
染色问题
跳马问题
算24点
图论算法
最小生成树算法(Prim算法)
单源最短路径算法(Dijkstra算法)
任意结点最短路径算法(Floyd算法)
求有向带权图的所有环
Bellman-Ford算法
计算图的连通性
计算最佳连通分支
计算拓扑序列
图论算法习题
网络建设问题
最短变换问题
挖地雷
乌托邦城市
乌托邦交通中心
动态规划
最短路径问题
动态规划概念
骑士游历问题
最长递增子序列
合唱队形
石子合并问题
能量项链
0/1背包问题
开心的金明
金明的预算方案
加分二叉树
字串编辑距离
花瓶插花
凸多边形三角划分
快餐店
⑷ C语言 拦截导弹
for (i=n-1;i>=1;i--)
{
for (j=n;j>=i+1;j--)
{
if (a[i]>a[j] && l[j]+1>l[i])
{
l[i]=l[j]+1;
}//printf("%d %d\n",i,j);}
max=0,ss=1;//for(i=1;i<=n;i++) printf("%d ",l[i]);printf("\n");
for (i=1;i<n;i++)
{
在这里有死循环，j永远小于i
---------------------------------------------------
/*
VC6.0编译运行成功
*/
#include
#include
/*
描述 Description
某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入格式 Input Format
输入数据只有一行，该行包含若干个数据，之间用半角逗号隔开，表示导弹依次飞来的高度（导弹最多有 20 枚，其高度为不大于 30000 的正整数）。
输出格式 Output Format
输出数据只有一行，该行包含两个数据，之间用半角逗号隔开。第一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。
样例输入 Sample Input
389,207,155,300,299,170,158,65
样例输出 Sample Output
6,1
其它测试输入样例
389,207,155,300,299,170,65,158
5,3,1,4,3,2,1,0
1,2,3,4,5,6,2
*/
/*
分析，问题是动态规划与Dilworth定理题目
http://www.gnocuil.cn/blog/article.asp?id=16
*/
int main()
{
char s[105];
int i, j, n, a[21], l[21], sign[21], max = 0, min = 0;
scanf("%s", s);
//min 代表最长递增序列长度 max 代表最短递减序列长度
for (i = 0, j = 0, a[0] = l[0] = sign[0] = 0; i < strlen(s); i++)
{
if (s[i] == ',')
{
a[++j] = 0;
sign[j] = 1;
l[j] = 1;
}
else
{
a[j] = a[j] * 10 + (s[i] - '0');
}
}
n = j;
for (i = n - 1; i >= 0; i--)
{
int maxflag = 0, minflag = 0;
j = i + 1;
while(j <= n)
{
if(a[i] > a[j])
{
if(l[i] < l[j])
{
l[i] = l[j];
}
maxflag = 1;
}
else if(a[i] < a[j])
{
if(sign[i] < sign[j])
{
sign[i] = sign[j];
}
minflag = 1;
}
j++;
}
if(maxflag)
l[i]++;
if(minflag)
sign[i]++;
if(max < l[i])
{
max = l[i];
}
if(min < sign[i])
{
min = sign[i];
}
}
printf("%d,%d\n", max, min - 1);
return (0);
}
⑸ 设计一个O（n的平方）时间的算法，找出由n个数组成的序列的最长单调递增子序列
用冒泡法 时间复杂度=O(n^2)
以 下是c语言版
#include <stdio.h>
main()
{int a[10];
int i,c,j;
for(i=0;i<10;i++)
{printf("请输入十个数,这是第%d个:",i+1);
scanf("%d",&a[i]);
}
for(i=0;i<10;i++)
{
for(j=10;j>i+1;j--)
{if(a[j-1]<a[j-2])
{c=a[j-1];
a[j-1]=a[j-2];
a[j-2]=c;
}
}
}
printf("从小到大的顺序是:");
for(i=0;i<10;i++)
{printf("\n%d",a[i]);
}
getch();
}
⑹ 一道ACM的题目，求用C语言递归编写的算法，非常感谢啊!!!：求上升子序列和的最大值
您好！
这是杭电acm的第1087题，答案如下：
#include<stdio.h>
__int64 a[10009],sum[10009],Maxsum,max;
int main()
{
int i,j,n;
while(scanf("%d",&n),n!=0)
{
for(i=0;i<n;i++)
scanf("%I64d",&a[i]);
sum[0]=a[0];
for(i=1;i<n;i++)
{ Maxsum=0;
for(j=0;j<i;j++)
if(a[i]>a[j])
{
if(Maxsum<sum[j])
Maxsum=sum[j];
}
sum[i]=Maxsum+a[i];
}
max=sum[0];
for(i=1;i<n;i++)
if(max<sum[i])
max=sum[i];
printf("%I64d\n",max);
}
return 0;
}
希望对您有帮助！
⑺ 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();
}
⑻ C语言中f=f*n表示什么意思
，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。时间复杂度用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1）常数阶；O（log2n）对数阶；O（n）线性阶；O（n2）平方阶。
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
二、算法设计的方法
1.递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。
阶乘计算
问题描述：编写程序，对给定的n（n≤100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。
由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a[ ]存储：
N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100
并用a[0]存储长整数N的位数m，即a[0]=m。按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素……。例如，5！=120，在数组中的存储形式为：
3 0 2 1 ……
首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。
计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。细节见以下程序。
# include <stdio.h>
# include <malloc.h>
......
2.递归
递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。
能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
编写计算斐波那契（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)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。
在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。
组合问题
问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，r=3的所有组合为： （1）5、4、3 （2）5、4、2 （3）5、4、1
（4）5、3、2 （5）5、3、1 （6）5、2、1
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数comb。
# include <stdio.h>
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
printf(“%4d”,a[j]);
printf(“\n”);
}
}
}
void main()
{ a[0]=3;
comb(5,3);
}
3.回溯法
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
组合问题
问题描述：找出从自然数1，2，…，n中任取r个数的所有组合。
采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：
（1） a[i+1]>a，后一个数字比前一个大；
（2） a-i<=n-r+1。
按回溯法的思想，找解过程可以叙述如下：
首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a[2]上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a[2]回溯到a[1]，这时，a[1]=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a[0]再回溯时，说明已经找完问题的全部解。按上述思想写成程序如下：
# define MAXN 100
int a[MAXN];
void comb(int m,int r)
{ int i,j;
i=0;
a=1;
do {
if (a-i<=m-r+1
{ if (i==r-1)
{ for (j=0;j<r;j++)
printf(“%4d”,a[j]);
printf(“\n”);
}
a++;
continue;
}
else
{ if (i==0)
return;
a[--i]++;
}
} while (1)
}
main()
{ comb(5,3);
}
4.贪婪法
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
例如平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币。按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解应是3个5单位面值的硬币。
装箱问题
问题描述：装箱问题可简述如下：设有编号为0、1、…、n-1的n种物品，体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0≤i＜n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。
若考察将n种物品的集合分划成n个或小于n个物品的所有子集，最优解就可以找到。但所有可能划分的总数太大。对适当大的n，找出所有可能的划分要花费的时间是无法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。不失一般性，设n件物品的体积是按从大到小排好序的，即有v0≥v1≥…≥vn-1。如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。装箱算法简单描述如下：
{ 输入箱子的容积；
输入物品种数n；
按体积从大到小顺序，输入各物品的体积；
预置已用箱子链为空；
预置已用箱子计数器box_count为0；
for (i=0;i<n;i++)
{ 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j；
if （已用箱子都不能再放物品i）
{ 另用一个箱子，并将物品i放入该箱子；
box_count++；
}
else
将物品i放入箱子j；
}
}
上述算法能求出需要的箱子数box_count，并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解，设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需三只箱子，各箱子所装物品分别为：第一只箱子装物品1、3；第二只箱子装物品2、4、5；第三只箱子装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。
若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。
}
5.分治法
任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题（1<k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。
6.动态规划法
经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。
为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。
求两字符序列的最长公共字符子序列
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：
（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；
（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；
（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
代码如下：
# include <stdio.h>
# include <string.h>
# define N 100
char a[N],b[N],str[N];
int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[0]=0;
for (i=0;i<=n;i++) c[0]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[j-1])
c[j]=c[i-1][j];
else
c[j]=c[j-1];
return c[m][n];
}
char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=’’;
while (k>0)
if (c[j]==c[i-1][j]) i--;
else if (c[j]==c[j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}
void main()
{ printf (“Enter two string（<%d）!\n”,N);
scanf(“%s%s”,a,b);
printf(“LCS=%s\n”,build_lcs(str,a,b));
}
7.迭代法
迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：
（1） 选一个方程的近似根，赋给变量x0；
（2） 将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；
（3） 当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。
若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为：
程序如下：
迭代法求方程组的根
{ for (i=0;i<n;i++)
x=初始近似根;
do {
for (i=0;i<n;i++)
y = x;
for (i=0;i<n;i++)
x = gi(X);
for (delta=0.0,i=0;i<n;i++)
if (fabs(y-x)>delta) delta=fabs(y-x)； } while (delta>Epsilon)；
for (i=0;i<n;i++)
printf(“变量x[%d]的近似根是 %f”，I，x)；
printf(“\n”)；
} 具体使用迭代法求根时应注意以下两种可能发生的情况：
（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；
（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。
8.穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。
将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。
程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的整数，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。程序如下：
按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形，每条边有4个变量的情况，程序的循环重数就要相应改变。
另外,虚机团上产品团购,超级便宜
⑼ 最长子序列算法的程序 要求用C语言!
有两种算法复杂度为O(n*logn)和O(n^2)
O(n^2)算法分析如下： （a[1]...a[n] 存的都是输入的数）
1、对于a[n]来说，由于它是最后一个数，所以当从a[n]开始查找时，只存在长度为1的不下降子序列；
2、若从a[n-1]开始查找，则存在下面的两种可能性：
（1）若a[n-1] < a[n] 则存在长度为2的不下降子序列 a[n-1],a[n].
（2）若a[n-1] > a[n] 则存在长度为1的不下降子序列 a[n-1]或者a[n]。
3、一般若从a[t]开始，此时最长不下降子序列应该是按下列方法求出的：
在a[t+1],a[t+2],...a[n]中，找出一个比a[t]大的且最长的不下降子序列，作为它的后继。
4、为算法上的需要，定义一个数组：
d:array [1..n,1..3] of integer;
d[t,1]表示a[t]
d[t,2]表示从i位置到达n的最长不下降子序列的长度
d[t,3]表示从i位置开始最长不下降子序列的下一个位置
最长不下降子序列的O(n*logn)算法分析如下：
先回顾经典的O(n^2)的动态规划算法，设A[t]表示序列中的第t个数，F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度，初始时设F[t] = 0(t = 1, 2, ..., len(A))。则有动态规划方程：F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。
现在，我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y]，满足
(1)x < y < t (2)A[x] < A[y] < A[t] (3)F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到同样的F[t]值，那么，在最长上升子序列的这个位置中，应该选择A[x]还是应该选择A[y]呢？
很明显，选择A[x]比选择A[y]要好。因为由于条件(2)，在A[x+1] ... A[t-1]这一段中，如果存在A[z]，A[x] < A[z] < a[y]，则与选择A[y]相比，将会得到更长的上升子序列。
再根据条件(3)，我们会得到一个启示：根据F[]的值进行分类。对于F[]的每一个取值k，我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值，即D[k] = min{A[t]} (F[t] = k)。
注意到D[]的两个特点：
(1) D[k]的值是在整个计算过程中是单调不上升的。
(2) D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。
利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A [t] > D[len]，则将A[t]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = A[t]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[t]。令k = j + 1，则有D[j] < A[t] <= D[k]，将A[t]接在D[j]后将得到一个更长的上升子序列，同时更新D[k] = A[t]。最后，len即为所要求的最长上升子序列的长度。
在上述算法中，若使用朴素的顺序查找在D[1]..D[len]查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与原来的算法相比没有任何进步。但是由于D[]的特点(2)，我们在D[]中查找时，可以使用二分查找高效地完成，则整个算法的时间复杂度下降为O(nlogn)，有了非常显着的提高。需要注意的是，D[]在算法结束后记录的并不是一个符合题意的最长上升子序列！
这个算法还可以扩展到整个最长子序列系列问题，整个算法的难点在于二分查找的设计，需要非常小心注意。
⑽ 用C语言解答
先按体重从小到大排序，同时记录下每个象的编号，然后从纸上中找出纸上递增的最长序列即可
有时间的话给楼主写出代码来，这不过年了么大家都忙，呵呵
花了点时间给楼主敲出代码了，累阿……
楼主体谅的加点分数吧 ^_^
有什么不懂的给我留言吧，希望对你有帮助
楼主最好告诉这题是在哪个OJ上的题目，以便我AC了，才能拿出100％的代码啊～
#include <stdio.h>
#include <stdlib.h>
int f[1002][1002];
int c[1002];//用来COPY智商以便于排序 to find LCS
int b[1002][1002];//用来记录象的编号，1代表XI＝＝YI，2代表
int t;
struct node
{
int wg;
int tel;
int num;
}a[1002];
int cmp1(const void* a,const void* b)//对结构体二级排序，当体重想同时按智商从小到大排
{
struct node*c=(struct node*)a;
struct node*d=(struct node*)b;
if(c->wg!=d->wg)
return c->wg - d->wg;
else
return c->tel - d->tel;
}
int cmp2(const void *a ,const void *b)
{
return *(int*)b - *(int*)a;
}
void print(int i,int j)//打印出号码
{
int y;
if(i==0||j==0)
return ;
if(b[i][j]==1)
{
print(i-1,j-1);
printf("%d\n",a[i-1].num+1);
}
else if(b[i][j]==2)
print(i-1,j);
else
print(i,j-1);
}
void delc()
{
int i,j,tmp;
for(i=0;i<t;i++)
{
tmp=c[i];
for(j=i+1;j<t-1;j++)
{
if(tmp==c[j])
c[j]= -1;//相当于把相同智商的去掉，只留下一个
}
}
}
int main()
{
int i,j,k;
int n,m;
scanf("%d",&t);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
b[i][j]=0;
for(i=0;i<t;i++)
{
scanf("%d%d",&a[i].wg,&a[i].tel);
c[i]=a[i].tel;
a[i].num=i;
}
qsort(a,t,sizeof(a[0]),cmp1);
qsort(c,t,sizeof(c[0]),cmp2);
//然后开找最长公共子序列
for(i=1;i<=t;i++)
{
f[i][0]=0;
f[0][i]=0;
}
for(i=1;i<=t;i++)
{
for(j=1;j<=t;j++)
{
if(a[i-1].tel==c[j-1])
{
f[i][j]=f[i-1][j-1]+1;
b[i][j]=1;
}
else if(f[i-1][j]>=f[i][j-1])
{
f[i][j]=f[i-1][j];
b[i][j]=2;
}
else if(f[i][j]<f[i][j-1])
{
f[i][j]=f[i][j-1];
b[i][j]=3;
}
}
}
delc();
printf("%d\n",f[t][t]);//个数
print(t,t);//对应的编号
return 0;
}