|
20、大数运算处理基本函数
#include<iostream>
#include<string>
using namespace std;
const int N = 1100;
struct big_num{
int ele[N];
int front;
};
typedef struct big_num bigNum;
void print_bigNum(const bigNum& num)
{
for(int i = num.front; i < N; ++i)
printf("%d", num.ele[i]);
}
void println_bigNum(const bigNum& num)
{
for(int i = num.front; i < N; ++i)
printf("%d", num.ele[i]);
printf("\n");
}
bigNum multi_bigNum(const bigNum& num1, const bigNum& num2)
{
bigNum temp;
bigNum num3;
int i, j, carry;
int temp_int;
num3.front = num1.front + num2.front - N;
for(i = num3.front; i < N; ++i)
num3.ele[i] = 0;
for(i = N - 1; i >= num1.front; --i)
{
carry = 0;
for(j = N - 1; j >= num2.front; --j)
{
temp_int = num2.ele[j] * num1.ele[i] + carry;
temp.ele[j] = temp_int % 10;
carry = temp_int / 10;
}
temp.front = num2.front;
if(carry != 0)
temp.ele[--temp.front] = carry;
carry = 0;
for(j = N - 1; j >= temp.front; --j)
{
temp_int = num3.ele[i + j + 1 - N] + temp.ele[j] + carry;
if(temp_int >= 10)
{
num3.ele[i + j + 1 - N] = temp_int - 10;
carry = 1;
}
else
{
num3.ele[i + j + 1 - N] = temp_int;
carry = 0;
}
}
while(carry == 1)
{
temp_int = num3.ele[i + j + 1 - N] + carry;
if(temp_int >= 10)
{
num3.ele[i + (j--) + 1 - N] = temp_int - 10;
carry = 1;
}
else
{
num3.ele[i + (j--) + 1 - N] = temp_int;
carry = 0;
}
}
}
while(num3.ele[num3.front] == 0 && num3.front < N - 1)
++num3.front;
return num3;
}
bigNum add_bigNum(const bigNum& num1, const bigNum& num2)
{
bigNum num3;
num3.front = num1.front;
if(num3.front < num2.front)
num3.front = num2.front;
int carry = 0;
int i;
for(i = N - 1; i >= num3.front; --i)
{
num3.ele[i] = num2.ele[i] + num1.ele[i] + carry;
carry = num3.ele[i] / 10;
num3.ele[i] %= 10;
}
if(num3.front == num2.front)
{
num3.front = num1.front;
for(; i >= num3.front; --i)
{
num3.ele[i] = num1.ele[i] + carry;
carry = num3.ele[i] / 10;
num3.ele[i] %= 10;
}
if(carry == 1)
{
--num3.front;
num3.ele[num3.front] = 1;
}
}
else
{
num3.front = num2.front;
for(; i >= num3.front; --i)
{
num3.ele[i] = num2.ele[i] + carry;
carry = num3.ele[i] / 10;
num3.ele[i] %= 10;
}
if(carry == 1)
{
--num3.front;
num3.ele[num3.front] = 1;
}
}
return num3;
}
void string_to_bigNum(bigNum& num, const char s[])
{
num.front = N - strlen(s);
for(int i = num.front; i < N; ++i)
num.ele[i] = s[i - num.front] - ''0'';
}
// 0 <= a <= 10
void muti_by_one(const bigNum& num1, int a, bigNum& num2)
{
int temp;
int carry = 0;
int i;
if(a == 0)
{
num2.ele[N - 1] = 0;
num2.front = N - 1;
return;
}
if(a == 10)
{
for(i = num1.front; i < N; ++i)
num2.ele[i - 1] = num1.ele[i];
num2.ele[N - 1] = 0;
num2.front = num1.front - 1;
}
for(i = N - 1; i >= num1.front; --i)
{
temp = a * num1.ele[i] + carry;
num2.ele[i] = temp % 10;
carry = temp / 10;
}
if(carry == 0)
num2.front = num1.front;
else
{
num2.front = num1.front - 1;
num2.ele[i] = carry;
}
}
int comp_bigNum(const bigNum& num1, const bigNum& num2)
{
int i;
if(num1.front != num2.front)
{
if(num1.front < num2.front)
return 1;
else
return -1;
}
for(i = num1.front; i < N; ++i)
if(num1.ele[i] != num2.ele[i])
{
if(num1.ele[i] > num2.ele[i])
return 1;
else
return -1;
}
return 0;
}
bool comp_bigNum_0(const bigNum& num1)
{
return (num1.ele[N - 1] == 0) && (num1.front == N - 1);
}
//这里只能让大数减小数，如果num1 < num2 则交换num1 和 num2 的顺序
bigNum minus_bigNum(const bigNum& num1, const bigNum& num2)
{
bigNum num3;
int temp;
int i;
temp = comp_bigNum(num1, num2);
if(temp < 0)
{
num3 = minus_bigNum(num2, num1);
return num3;
}
if(temp == 0)
{
num3.front = N - 1;
num3.ele[N - 1] = 0;
return num3;
}
int carry = 0;
for(i = N - 1; i >= num2.front; --i)
{
temp = num1.ele[i] - num2.ele[i] - carry;
if(temp < 0)
{
temp += 10;
carry = 1;
}
else
carry = 0;
num3.ele[i] = temp;
}
while(i >= num1.front)
{
temp = num1.ele[i] - carry;
if(temp < 0)
{
temp += 10;
carry = 1;
}
else
carry = 0;
num3.ele[i] = temp;
--i;
}
num3.front = num1.front;
while(num3.ele[num3.front] == 0)
++num3.front;
return num3;
}
//需要再调用前检查num2是否为0
bigNum div_bigNum(const bigNum& num1, const bigNum& num2, bigNum& num4)
{
bigNum num3;
if(comp_bigNum(num1, num2) < 0)
{
num4 = num1;
num3.front = N - 1;
num3.ele[N - 1] = 0;
return num3;
}
int num[N];
int num_end = 0;
int num1_cur = num1.front + N - 1 - num2.front;
int i;
bigNum temp_bigNum;
bigNum cut_bigNum;
bigNum pre_bigNum;
cut_bigNum.front = num2.front + 1;
for(i = num1.front; i < num1_cur; ++i)
cut_bigNum.ele[cut_bigNum.front + i - num1.front] = num1.ele[i];
while(num1_cur < N)
{
if(!comp_bigNum_0(cut_bigNum))
{
for(i = cut_bigNum.front; i < N; ++i)
cut_bigNum.ele[i - 1] = cut_bigNum.ele[i];
--cut_bigNum.front;
}
cut_bigNum.ele[N - 1] = num1.ele[num1_cur++];
temp_bigNum.front = N - 1;
temp_bigNum.ele[N - 1] = 0;
for(i = 1; i <= 10; ++i)
{
pre_bigNum = temp_bigNum;
muti_by_one(num2, i, temp_bigNum);
if(comp_bigNum(temp_bigNum, cut_bigNum) > 0)
break;
}
num[num_end++] = i - 1;
cut_bigNum = minus_bigNum(cut_bigNum, pre_bigNum);
}
num4 = cut_bigNum;
num3.front = N;
for(i = num_end - 1; i >= 0; --i)
num3.ele[--num3.front] = num[i];
while(num3.ele[num3.front] == 0)
++num3.front;
return num3;
}/*
void print_bigNum(const bigNum&);
void println_bigNum(const bigNum& num);
bigNum multi_bigNum(const bigNum& num1, const bigNum& num2);
bigNum add_bigNum(const bigNum& num1, const bigNum& num2);
void string_to_bigNum(bigNum& num, const char s[]);
void muti_by_one(const bigNum& num1, int a, bigNum& num2);
int comp_bigNum(const bigNum& num1, const bigNum& num2);
bool comp_bigNum_0(const bigNum& num1);
bigNum minus_bigNum(const bigNum& num1, const bigNum& num2);
bigNum div_bigNum(const bigNum& num1, const bigNum& num2, bigNum& num4);*/
int main()
{
bigNum num1, num2, num3, num4;
char s[550];
while(cin >> s)
{
string_to_bigNum(num1, s);
cin >> s;
string_to_bigNum(num2, s);
num3 = div_bigNum(num1, num2, num4);
println_bigNum(num3);
}
return 0;
}
21、背包问题的递归算法
/*背包问题的递归算法 */
#include<stdio.h>
//物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了
#define N 100
int n ;
//物品总种数
double limitW ;
//限制的总重量
double totV ;
//全部物品的总价值
double maxv ;
//解的总价值
int option[N];
//解的选择
int cop[N];
//当前解的选择
struct
{
//物品结构
double weight ;
double value ;
}a[N];
//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值
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)
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 ;
}
}
}
void main()
{
int k ;
double w,v ;
printf("输入物品种数:");
scanf("%d",&n);
printf("输入各物品的重量和价值:");
for(totV=0.0,k=0;k<n;++k)
{
scanf("%lf %lf",&w,&v);
a[k].weight=w ;
a[k].value=v ;
totV+=v ;
}
printf("输入限制重量:");
scanf("%lf",&limitW);
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("%4d",k+1);
printf("总价值为: %2f",maxv);
}
22、N皇后问题
/*N皇后问题 */
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
int N ;
int*blow ;
int**a ;
int fun(int r,int l)
{
int i,j ;
for(i=0;i<N;i++)
if(a[i][l]==1||a[r][i]==1)return 0 ;
for(i=r,j=l;i>=0&&j>=0;i--,j--)
if(a[i][j]==1)return 0 ;
for(i=r,j=l;i<N&&j<N;i++,j++)
if(a[i][j]==1)return 0 ;
for(i=r,j=l;i>=0&&j<N;i--,j++)
if(a[i][j]==1)return 0 ;
for(i=r,j=l;i<N&&j>=0;i++,j--)
if(a[i][j]==1)return 0 ;
return 1 ;
}
int main()
{
int i,j ;
int row=0,low=0 ;
/*行，列*/
printf("Enter the N:\n");
scanf("%d",&N);
/*C语言动态申请问题*/
blow=(int*)malloc(N*sizeof(int));
a=(int**)malloc(N*sizeof(int*));
for(i=0;i<N;i++)
a[i]=(int*)malloc(N*sizeof(int));
/*C语言动态申请问题*/
for(i=0;i<N;i++)
for(j=0;j<N;j++)
a[i][j]=0 ;
while(1)
{
if(fun(row,low))
{
a[row][low]=1 ;
blow[row]=low ;
row++;
low=0 ;
}
else
low++;
if(row>=N)break ;
while(low>=N)
{
row--;
low=blow[row];
a[row][low]=0 ;
low++;
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(a[i][j])printf("Q");
else
printf("o");
}
printf("\n");
}
getch();
}
23、并查集及应用
/******************************************************************************
数据结构——并查集及应用
并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。
一般采取树形结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。
这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，
N次合并M查找的时间复杂度为O(M Alpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内（人类目前观测到的宇宙范围估算有10的80次方个原子，这小于前面所说的范围）这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是线性的。
******************************************************************************/
int set[MAXN],rank[MAXN];
int FindSet(int x)
{
if(set[x]!=x)
set[x]=FindSet(set[x]);
return set[x];
}
void MakeSet(int x)
{
set[x]=x;
rank[x]=0;
}
void Link(int a,int b)
{
if(rank[a]>rank[b])
set[b]=a;
else if(rank[a]<rank[b])
set[a]=b;
else
{
set[a]=b;
rank[b]++;
}
}
void Union(int a,int b)
{
Link(FindSet(a),FindSet(b));
}
这是通过并查集实现kruskal算法求图的最小生成树的例子：
以下内容为程序代码:
#include "stdio.h"
#include "string.h"
#define INFIN 30000
#define MAXN 10
int set[MAXN],rank[MAXN];
int FindSet(int x)
{
if(set[x]!=x)
set[x]=FindSet(set[x]);
return set[x];
}
void MakeSet(int x)
{
set[x]=x;
rank[x]=0;
}
void Link(int a,int b)
{
if(rank[a]>rank[b])
set[b]=a;
else if(rank[a]<rank[b])
set[a]=b;
else
{
set[a]=b;
rank[b]++;
}
}
void Union(int a,int b)
{
Link(FindSet(a),FindSet(b));
}
int main()
{
int n,k,i,j,map[MAXN][MAXN];
int t1,t2,t3,cost=0;
memset(map,0,sizeof(map));
scanf("%d %d",&n,&k);
while(k--)
{
scanf("%d %d %d",&t1,&t2,&t3);
map[t1][t2]=map[t2][t1]=t3;
}
for(i=0;i<n;i++)
MakeSet(i);
for(k=1;k<n;k++)
{
t3=INFIN;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(map[i][j] && FindSet(i)!=FindSet(j))
if(map[i][j]<t3)
{
t1=i;t2=j;t3=map[i][j];
}
cost+=t3;
Union(t1,t2);
}
printf("%d\\n",cost);
return 0;
}
24、大数阶乘
/ * n! = 1 * 2 * 3 * .... * n → lg(n!) = lg(1 * 2 * 3 * .... * n) = lg(1) + lg(2) + lg(3) + .. + lg(n)
→ n! = 10^(lg(1) + lg(2) + lg(3) + .. + lg(n))
考虑到当n很大时，输出具体的结果并无多大实际意义，遂另写代码如下： * /
Sub calcfactorial(ByVal num As Long, Optional ByRef POWER As String, Optional ByRef FIRSTNUM As String)
Dim I As Long, TEMP As Double, temp2 As Long, STIME As Single
TEMP = 0
temp2 = 0
STIME = Timer
For I = 1 To num
TEMP = TEMP + Log(I) / Log(10)
If TEMP > 1000000 Then
temp2 = temp2 + 1
TEMP = TEMP - 1000000
End If
Next
POWER = Format(Int(TEMP + 1), "000000")
TEMP = TEMP - Val(POWER)
POWER = temp2 & POWER
If Val(POWER) < 10 ^ 6 Then POWER = Val(POWER)
FIRSTNUM = Left(Replace(10 ^ (TEMP), ".", ""), 10)
Debug.Print Right(Space(9) & num, 9) & "！ ： 用时 " & Right(Space(8) & Format(Timer - STIME, "0.00000"), 8) & " 秒, 结果 " & Right(Space(10) & POWER, 10) & " 位,前10位为 " & FIRSTNUM
End Sub
Private Sub Command1_Click()
Dim I As Long, J As Long
For J = 2 To 7
For I = 1 To 10
calcfactorial I * 10 ^ J
Next
Debug.Print
Next
End Sub
25、最短路问题总结
Dijkstra:
w[i,j]表示i,j的权
s[i,j]表示i到j的最短路
开始置源点检查标志
repeat
i-检查过的点,j-未检查过的点,且min(w[i,j]),置j检查标志，此时j的最短路确定
修改所有以j为起点的边，if s[o,j]+s[j,k]<s[o,k] then s[o,k]:=s[o,j]+s[j,k]
until 所有的点都检查过
注意，这种算法只适用于权没有负的情况下，时间复杂度O((n+e)log(2,n))，其中n是点数，e是边数
Bellman-Ford:
w[i,j]表示i,j的权
s[i,j]表示i到j的最短路
repeat
for 所有边[i,j]
if s[o,i]+w[i,j]<s[o,j] then 更新s[o,j]
until 没有改变
这种算法适用于所有类型的图，时间复杂度为O(ne)
以上两种方法都是求单源最短路问题(SSSP)的，如过要求任两个点的最短路径(APSP)，则要重复n次，下面介绍一种求新算法
Floyd-Warshall:
s[i,j]表示i到j的最短路
for k 所有点
for i 所有点
for j 所有点
if s[i,k]+s[k,j]<s[i,j] then 更新s[i,j]
这种算法只适用于没有负权的情况，时间复杂度为O(N^3)
26、二叉树的一些算法
（１） 求二叉树结点数目的算法．
typedef struct node
{
char data;
struct node *lchild，*rchild;
}NODE;
int nodenumber(NODE *root)
{
if(root<=NULL)return(0);
else return(1+nodenumber(root->lchild)+nodenuber(root->rchild);
}
（２） 输出二叉树所有叶子的算法．
void showleaves(NODE *root)
{
if(root==NULL)return;
if(root->lchild==NULL&&root->rchild==NULL)
{ printf("%c",root->data);
return;
}
else if(root->lchild!=NULL)showleaves(root->lchid);
if(root->rchild!=NULL)showleaves(root->rchild);
}
（３） 求二叉树深度的算法．
int Treedepth(NODE *root)
{ if(root->NULL)return(-1);
if(root->lchild==NULL&&(root->rchild==NULL)return(0);
else return(Treedepth(root->lchild)>Treedepth(root->rchild)?
(1+Treedepth(root->lchild)):(1+Treedepth(root->rchild));
}
（４） 将树中所有节点的左右子树交换的算法．
void Treeswap(NODE *root){
if(root==NULL|(root->lchild==NULL&&root->rchild==NULL)return;
p=root->lchild;
root->lchild=root->rchild;
root->rchild=p;
Treeswap(root->lchild);
Treeswap(root->rchild);
}
（５） 按层次顺序（同一层次从左到右）遍历二叉树的算法．
void levorder(NODE *t,int m)
{ NODE *q[100],*p;
int head,tail,i;
q[0]=t;
head=0;
tail=1;
while(head<tail)
{ p=q[head++];
printf("%c",p->data);
for(i=0;i<m;i++)]
if(p->child[i]!=NULL)
q[tail++]=p->child[i];
} }
（６） 复制这棵二叉树的算法．
NODE*copytree(NODE *root) {
NODE *p
if(root==NULL)return(NULL);
else p=(NODE*)malloc(sizeof(NODE));
p->data=root->data;
p->lchild=copytree(root->lchild);
p->rchild=copytree(root->rchild);
return(p);
}
27、阶乘后面有几个零
#include <iostream>
using namespace std ;
int countzero(int st,int dt){
int count=0 ;
int i ;
for(i=st;i<=dt;++i) {
int temp=i ;
while(temp%5==0) {
++count ;
temp/=5 ;
}
}
return count ;
}
int main(){
int n ;
cout<<"请输入n"<<endl ;
cin>>n ;
cout<<countzero(1,n)<<endl ;
system("PAUSE");
return 0 ;
}
28、牛顿法求平方根和立方根
例题：采用牛顿法求平方根
给定一个正数x，如何计算x的平方根呢？
牛顿的逐步逼近法
对于x的平方根，给定一个猜测值y，则y与x/y的平均值是比y更好的一个猜测值，继续这一过程，会得到越来越好的猜测值。
如何用过程语言表述这一计算过程？
初始条件：给定 x 和 猜测值 guess
sqrt(guess,x){
if(goodEnough(guess,x)) return guess;
return sqrt(improve(guess,x),x);
}
goodEnough(guess,x){
if(abs(guess*guess-x)<threshold) return true;
return false;
}
Improve(guess,x){ return (guess+x/guess)/2; }
这个例子体现了可以通过一个过程递归的方法得到越来越好的猜测值;可以把过程抽象成一个个的黑箱,来完成不同的操作，过程的抽象一方面隐蔽了一些细节，使求解的过程更清晰，另一方面可以通过局部的修改改进整个求值过程的功能；
例如，通过修改goodEnough里面的threshold就可以改变求解的精度，而不必修改其它部分。
求立方根的牛顿法基于如下事实，如果y是x的立方根的一个近似值，那么下式将给出一个更好的近似值：
(x/y2+2y)/3
请利用这一公式实现一个类似平方根过程的求立方根的过程。
代码:
#include<stdio.h>
#include <math.h>
float fun(float guess,float x){
if(abs(guess*guess*guess-x)<0.0000001) return guess;
else
return fun((x/guess/guess+2*guess)/3,x);
}
int main(){
float a,b;
while(scanf("%f%f",&a,&b));
printf("%f\n",fun(a,b));
}
29、数划分问题
设S是一个具有n个元素的集合s={a1,a2,…,an},现将s集合划分成K个满足下列条件的子集s1,s2,…,sk:
1.si 不能为空
2si与sj的交集为空
3.所有子集的并集为S
则称s1,s2,…,sn是s的一个划分.它相当于把s集合中的n个a1,…an放入k个无标号的盒子中,使得没有一个盒子为空,试确定n个a1…an放入k 个无标号盒子的s(n,k)
有两种互不相容的情况:
1){an}是k个子集中的一个:s(n-1,k-1)
2) ){an}不是k个子集中的一个:k*s(n-1,k)
递归关系为:
s(n,k)=s(n-1,k-1)+k*s(n-1,k) (n>k,k>=1)
s(n,k)=0 (n<k)或(k=n<n)
s(n,k)=1 (k=1)或(k=n)
背包问题
设有一个背包,可以放入的重量为s.现有n件物品重量分别为w1,w2,…,wn,并假设wi(1<=i<=n)均为正整数,且顺序存放在w中(w:array[1..n] of intteger).现要求设计一个布尔函数knap(s0,n0),如果从这n件物品中选择n0件放入此背包,使得放入的重量之和正好为s0,函数返回true,并输出一组被选中的各物品的重量.否则函数返回false.
边界条件:
只要不选任何物品放入包:
s=0 kanp(s,n)=true
无论如何选,不能使重量为负:
s<0 kanp(s,n)=false
不取任何东西不可能重量为负:
s>0且n<1 kanp(s,n)=false
递归体:
当选择的物品中不包含Wn
kanp(s,n)= knap(s,n-1)
当选择的物品中包含Wn,即knap(s-w[n],n-1)=true:
kanp(s,n)= knap(s-wn,n-1)
30、全排列
#include <stdio.h>
#include <stdlib.h>
int number[20], len, temp;
void output(){
int i;
printf("\n");
for(i=0; i<len; ++i)
printf("%d ", number[i]);
}
int pailie(int n){
int ii;
if(n==len)
output( );
for(ii=n; ii<len; ++ii) {
temp = number[ii]; number[ii] = number[n]; number[n] = temp;
pailie(n+1);
temp = number[ii]; number[ii] = number[n]; number[n] = temp;
}
return 0;
}
int main(int argc, char *argv[]){
int index = 0;
scanf("%d", &len);
while(index<len)
scanf("%d", &number[index++]);
pailie(0);
system("PAUSE");
return 0;
}
31、数据组合
/*编写一个函数如下，要求返回从小于B的正整数中任选任意多个数加起来和等于A的组合数。要求写出递规算法。//int func(unsigned int A,unsigned int B) */
#include<iostream>
using namespace std;
int func(unsigned int A,unsigned int B){
if( (A<1) || (B<1) ) return 0;
if( (A==1) || (B==1) ) return 1;
if(A<B) return func(A, A);
if(A==B) return (func(A, B-1)+1);
return (func(A, B-1) + func(A-B, B));
}
int main(){
int a,b;
cin>>a>>b;
cout<<func(a,b-1)<<endl;
system("PAUSE");
return 0;
}//来自一位网友的回复
//=====================================================================
#include <iostream>
#include <cstdlib>
using namespace std;
int total=0;
void make(int a,int b,int start){
if(a==0){total++; return;}
if(a<0) return;
if(start==b-1) return;
int maxs =a/(++start);
int i=0;
for(int i=0;i<=maxs;i++)make(a-i*start,b,start);
}
int main(int argc, char *argv[]){
int a,b,start=0;
cout<<"请输入a,b值"<<endl;
cin>>a>>b;
make(a,b,start);
cout<<total<<endl;
system("PAUSE");
return 0;
}//我自己的.
32、/*字符串中添加n个''-''的所有情况. */
#include<stdio.h>
#include <string.h>
int fun(char*s,int n,int l){
char s1[100];
int i,j ;
if(l==0){
printf("%s\n",s);
return 0 ;
}
strcpy(s1,s);
for(i=0;i<=n;i++){
strcpy(s1,s);
for(j=n-1;j>=i;j--)
s1[j+1]=s1[j];
s1[i]=''-'' ;
s1[n+1]=''\0'' ;
fun(s1,n+1,l-1);
}
}
int main(){
char a[100];
int i,len ;
scanf("%d%s",&len,a);
fun(a,strlen(a),len);
getch();
}
33、位操作技巧
/******************************************************************/
检测一个无符号数是不为2^n-1(^为幂)： x&(x+1)
将最右侧0位改为1位： x | (x+1)
二进制补码运算公式：
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x - ~y - 1 = (x|y)+(x&y)
x-y = x + ~y + 1 = (x|~y)-(~x&y)
x^y = (x|y)-(x&y)
x|y = (x&~y)+y
x&y = (~x|y)-~x
x==y: ~(x-y|y-x)
x!=y: x-y|y-x
x< y: (x-y)^((x^y)&((x-y)^x))
x<=y: (x|~y)&((x^y)|~(y-x))
x< y: (~x&y)|((~x|y)&(x-y))//无符号x,y比较
x<=y: (~x|y)&((x^y)|~(y-x))//无符号x,y比较
使用位运算的无分支代码：
计算绝对值
int abs( int x ) {
int y ;
y = x >> 31 ;
return (x^y)-y ;//or: (x+y)^y
}
符号函数：sign(x) = -1, x<0; 0, x == 0 ; 1, x > 0
int sign(int x){
return (x>>31) | (unsigned(-x))>>31 ;//x=-2^31时失败(^为幂)
}
三值比较：cmp(x,y) = -1, x<y; 0, x==y; 1, x > y
int cmp( int x, int y ){
return (x>y)-(x-y) ;
}
doz=x-y, x>=y; 0, x<y
int doz(int x, int y ){
int d ;
d = x-y ;
return d & ((~(d^((x^y)&(d^x))))>>31) ;
}
int max(int x, int y ) {
int m ;
m = (x-y)>>31 ;
return y & m | x & ~m ;
}
不使用第三方交换x,y:
1.x ^= y ; y ^= x ; x ^= y ;
2.x = x+y ; y = x-y ; x = x-y ;
3.x = x-y ; y = y+x ; x = y-x ;
4.x = y-x ; x = y-x ; x = x+y ;
双值交换:x = a, x==b; b, x==a//常规编码为x = x==a ? b :a ;
1.x = a+b-x ;
2.x = a^b^x ;
下舍入到2的k次方的倍数:
1.x & ((-1)<<k)
2.(((unsigned)x)>>k)<<k
上舍入：
1. t = (1<<k)-1 ; x = (x+t)&~t ;
2.t = (-1)<<k ; x = (x-t-1)&t ;
位计数,统计1位的数量：
1.int pop(unsigned x){
x = x-((x>>1)&0x55555555) ;
x = (x&0x33333333) + ((x>>2) & 0x33333333 ) ;
x = (x+(x>>4)) & 0x0f0f0f0f ;
x = x + (x>>8) ;
x = x + (x>>16) ;
return x & 0x0000003f ;
}
2.int pop(unsigned x) {
static char table[256] = { 0,1,1,2, 1,2,2,3, ...., 6,7,7,8 } ;
return table[x&0xff]+table[(x>>8)&0xff]+table[(x>>16)&0xff]+table[(x>>24)] ;
}
奇偶性计算:
x = x ^ ( x>>1 ) ;
x = x ^ ( x>>2 ) ;
x = x ^ ( x>>4 ) ;
x = x ^ ( x>>8 ) ;
x = x ^ ( x>>16 ) ;
结果中位于x最低位，对无符号x,结果的第i位是原数第i位到最左侧位的奇偶性
位反转：
unsigned rev(unsigned x){
x = (x & 0x55555555) << 1 | (x>>1) & 0x55555555 ;
x = (x & 0x33333333) << 2 | (x>>2) & 0x33333333 ;
x = (x & 0x0f0f0f0f) << 4 | (x>>4) & 0x0f0f0f0f ;
x = (x<<24) | ((x&0xff00)<<8) | ((x>>8) & 0xff00) | (x>>24) ;
return x ;
}
递增位反转后的数：
unsigned inc_r(unsigned x){
unsigned m = 0x80000000 ;
x ^= m ;
if( (int)x >= 0 )
do { m >>= 1 ; x ^= m ; } while( x < m ) ;
return x ;
}
混选位：
abcd efgh ijkl mnop ABCD EFGH IJKL MNOP->aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP
unsigned ps(unsigned x){
unsigned t ;
t = (x ^ (x>>8)) & 0x0000ff00; x = x ^ t ^ (t<<8) ;
t = (x ^ (x>>4)) & 0x00f000f0; x = x ^ t ^ (t<<4) ;
t = (x ^ (x>>2)) & 0x0c0c0c0c; x = x ^ t ^ (t<<2) ;
t = (x ^ (x>>1)) & 0x22222222; x = x ^ t ^ (t<<1) ;
return x ;
}
位压缩：
选择并右移字x中对应于掩码m的1位的位,如：compress(abcdefgh,01010101)=0000bdfh
compress_left(x,m)操作与此类似，但结果位在左边: bdfh0000.
unsigned compress(unsigned x, unsigned m){
unsigned mk, mp, mv, t ;
int i ;
x &= m ;
mk = ~m << 1 ;
for( i = 0 ; i < 5 ; ++i ) {
mp = mk ^ ( mk << 1) ;
mp ^= ( mp << 2 ) ;
mp ^= ( mp << 4 ) ;
mp ^= ( mp << 8 ) ;
mp ^= ( mp << 16 ) ;
mv = mp & m ;
m = m ^ mv | (mv >> (1<<i) ) ;
t = x & mv ;
x = x ^ t | ( t >> ( 1<<i) ) ;
mk = mk & ~mp ;
}
return x ;
}
位置换：
用32个5位数表示从最低位开始的位的目标位置，结果是一个32*5的位矩阵，
将该矩阵沿次对角线转置后用5个32位字p[5]存放。
SAG(x,m) = compress_left(x,m) | compress(x,~m) ;
准备工作：
void init( unsigned *p ) {
p[1] = SAG( p[1], p[0] ) ;
p[2] = SAG( SAG( p[2], p[0]), p[1] ) ;
p[3] = SAG( SAG( SAG( p[3], p[0] ), p[1]), p[2] ) ;
p[4] = SAG( SAG( SAG( SAG( p[4], p[0] ), p[1]) ,p[2]), p[3] ) ;
}
实际置换：
int rep( unsigned x ) {
x = SAG(x,p[0]);
x = SAG(x,p[1]);
x = SAG(x,p[2]);
x = SAG(x,p[3]);
x = SAG(x,p[4]);
return x ;
}
二进制码到GRAY码的转换:
unsigned B2G(unsigned B ){
return B ^ (B>>1) ;
}
GRAY码到二进制码:
unsigned G2B(unsigned G){
unsigned B ;
B = G ^ (G>>1) ;
B = G ^ (G>>2) ;
B = G ^ (G>>4) ;
B = G ^ (G>>8) ;
B = G ^ (G>>16) ;
return B ;
}
找出最左0字节的位置:
int zbytel( unsigned x ){
static cahr table[16] = { 4,3,2,2, 1,1,1,1, 0,0,0,0, 0,0,0,0 } ;
unsigned y ;
y = (x&0x7f7f7f7f) + 0x7f7f7f7f ;
y = ~(y|x|0x7f7f7f7f) ;
return table[y*0x00204081 >> 28] ;//乘法可用移位和加完成
}
34、大数阶乘的计算
#include "Stdio.h"
#include "Stdlib.h"
#include "Math.h"
#define UNREFERENCED_PARAMETER(p) (p)
/******************************************************************************
功能 : 计算(Number!)存储时所需要的内存空间大小(其中一位占用一个int空间)
参数 : int Number
返回值 : 参数输入合法时返回(Number!)所需要的字节数，否则将返回0
典型用法 : int nSize = GetResultSize(100);
******************************************************************************/
int GetResultSize(int Number){
int i = 0;
double dSize = 1.0; //这里不能为整型，否则会损失精度从而导致计算结果不正确
if(Number < 1) {//如果输入的参数非法，为负或者0
return 0L;
}
/* 原理：位数 = log10(n!) + 1 => 1 + log10(1) + log10(2) + ...... + log10(n) */
for(i = 1; i <= Number; i++) {
dSize += (log10(i));
}
return ((dSize > 0)? (int)dSize : 0);
}
*******************************************************************************
功能 : 动态分配nSize个整数所需内存空间大小的堆
参数 : int nSize
返回值 : 参数输入合法时返回所分配堆的指针，否则将返回NULL
典型用法 : int *pBuffer = AllocResultBuffer(nSize);
******************************************************************************/
int* AllocResultBuffer(int nSize){
int *pBuffer = NULL;
if(nSize > 0) {
pBuffer = (int*)malloc(sizeof(int) * nSize);
}
return pBuffer;
}
*******************************************************************************
功能 : 释放*pBuffer所指向的动态分配的堆，并将*pBuffer指针设置为NULL
参数 : int **pBuffer
典型用法 : ReleaseResultBuffer(&pBuffer);
******************************************************************************/
void ReleaseResultBuffer(int **pBuffer){
if(pBuffer) {
free(*pBuffer);
*pBuffer = NULL;
}
}
*******************************************************************************
功能 : 显示pBuffer所指向的堆中所存放的整数数组，并且位数为nResultSize
参数 : int *pBuffer(堆指针), int nResultSize(位数)
典型用法 : DisplayResult(pBuffer, nResultSize);
******************************************************************************/
void DisplayResult(int *pBuffer, int nResultSize){
int i = 0;
//结果是从高位开始，高位存放结果的高位，地位存放结果的低位
for(i = (nResultSize - 1); i >= 0; i--) {
printf("%d", pBuffer[i]);
}
putchar(''\n'');
system("pause");
}
/******************************************************************************
功能 : 计算(Number!)的阶乘，并将结果存放到pResultBuf所指向的堆中，
位数存放到nSize所指向的整数中
参数 : int *pResultBuf(存放结果的堆), int nBufSize(堆的空间大小),
int *pnSize(计算结果的位数), int Number(所要计算输入值)
典型用法 : factorial(pResultBuf, nBufSize, &nSize, Number);
******************************************************************************/
#pragma warning(disable : 4013)
void factorial(int *pResultBuf, int nBufSize, int *pnSize, int Number){
int i = 0, j = 0, inc = 0;
//结果初始化
memset(pResultBuf, 0, (sizeof(int) * nBufSize));
pResultBuf[0] = 1;
*pnSize = 1; //位数初始化为1
for(i = 1; i <= Number; i++) {
//逐个乘以每位
for(j = 0; j < (*pnSize); j++){
pResultBuf[j] *= i;
pResultBuf[j] += inc;
inc = (pResultBuf[j] / 10);
pResultBuf[j] %= 10;
}
//处理最高位的溢出
while(inc > 0){
pResultBuf[j] += inc;
inc = (pResultBuf[j] / 10);
pResultBuf[j] %= 10;
(*pnSize)++;
j++;
}
}
}
void main(void){
int Number = 0;
int nBufferSize = 0, nResultSize = 0;
int* ResultBuffer = NULL;
do {
system("cls");
printf("This is a factorial calculator.\n");
printf("Please input the Number for calculating the Number, 0 for exit: ");
flushall();
scanf("%d", &Number);
putchar(''\n'');
if(Number == 0)
break;
ResultBuffer = AllocResultBuffer((nBufferSize = GetResultSize(Number)));
if(NULL == ResultBuffer) {
printf("\nThe Number you input is illegal!\n");
system("pause");
continue;
}
printf("Please wait...");
factorial(ResultBuffer, nBufferSize, &nResultSize, Number);
printf("\nThe result is: ");
DisplayResult(ResultBuffer, nResultSize);
ReleaseResultBuffer(&ResultBuffer);
} while(Number != 0);
}
35、骑士周游算法分析
/*======================用链栈实现=============*/
/*算 法 思 想 ：主 要 用 链 栈 实 现 ， 即 用 单 链 表 来 实 现 栈 结 构 。 与 双 向 链 表 实 现 区 别 仅 在 于 push 和 pop 操 作*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdio.h>
#define LEN sizeof(struct stack)
struct stack {
int row ;
int col ;
int dir ;
struct stack*next ;
};
struct stack*head=(struct stack*)malloc(LEN);
struct stack*q=head ;
void push(int i,int j,int v){
struct stack*p=(struct stack*)malloc(LEN);
p->row=i ;
p->col=j ;
p->dir=v ;
p->next=q ;
q=p ;
}
void pop(){
struct stack*temp ;
temp=q->next ;
free(q);
q=temp ;
}
void start(){
int y,z,v=0 ;
int i,j ;
int move[8][2]={ 2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1 } ;
int c[6][6];
for(i=0;i<6;i++) {
for(j=0;j<6;j++)
c[j]=0 ;
}
printf("input y:");
scanf("%d",&y);
printf("input z:");
scanf("%d",&z);
int account=0 ;
while(account<35){
while(v<8){
i=y+move[v][0];
j=z+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0){
push(y,z,v+1);
account++;
c[y][z]=account ;
y=i ;
z=j ;
v=0 ;
}
else v++;
}
if(v==8&&account>0&&account!=35){
y=q->row ;
z=q->col ;
v=q->dir ;
pop();
// y=stack[top][0];
// z=stack[top][1];
// v=stack[top][2];
c[y][z]=0 ;
account--;
}
}
c[y][z]=36 ;
for(i=0;i<6;i++){
for(j=0;j<6;j++){
printf("%4d",c[j]);
}
printf("\n");
}
}
void main(){
printf("\n");
start();
}
/*=================骑士周游算法分析--用数组实现==================*/
/*算 法 思 想 :用 一 个 二 维 的 数 组 stack[36][3]充 当 栈 的 作 用,用 来 记 录 36 个 位 置 的 行,列,以 及 方 向.设 置 全 程 标 量 top,用 来 指 向 当 前 位 置.用 push()和 pop()函 数 分 别 实 现 压 栈 和 出 栈.start()函 数 则 是 具 体 实 现 骑 士 周 游 算 法 的 函 数.具 体 思 想 见 注 释.*/
#include<stdio.h>
#include<conio.h>
#include<stdio.h>
int stack[36][3];
//设置一个全程的数组
int top=0 ;
//设置全程的变量top.
//push()函数用来表示压栈操作
void push(int i,int j,int k){
stack[top][0]=i ;
stack[top][1]=j ;
stack[top][2]=k ;
top++;
}
//pop（）函数用来表示出栈操作
void pop(){
top--;
}
//start()函数用来具体执行骑士周游的算法
void start(){
int y,z,v=0 ;
int i,j ;
int move[8][2]= { 2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1 };
//设置8个方向
int c[6][6];
//设置一个二维数组，用来打印出周游的具体路线
for(i=0;i<6;i++){
for(j=0;j<6;j++)
c[j]=0 ;
}
//初始化数组
printf("input y:");
scanf("%d",&x);
printf("input z:");
scanf("%d",&y);
//由用户输入初始起跳位置
int account=0 ;
//设置一个计数器，用来清楚的显示骑士走的路线
while(account<35){
while(v<8) {
i=x+move[v][0];
j=y+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0) {
push(x,y,v+1);
//若一个位置可走，则把前一个位置及下一个要走的方向压栈
account++;
c[x][y]=account ;
x=i ;
y=j ;
v=0 ;
}
else v++;
//若一个位置走不通，则换一个方向再试
}
//加入8个方向全已经走过，则弹出刚进栈 的 那 个 元 素 。
if(v==8&&account>0&&account!=35) {
pop();
// y=q->row;
// z=q->col;
// v=q->dir;
x=stack[top][0];
y=stack[top][1];
v=stack[top][2];
c[x][y]=0 ;
//由于已经把c[x][y]上的元素弹出，则把该位置清零。
account--;
}
}
c[x][y]=36 ;
//把最后一个元素置为36。
//打印周游路线
for(i=0;i<6;i++){
for(j=0;j<6;j++){
printf("%4d",c[j]);
}
printf("\n");
}
}
void main(){
printf("\n");
start();
}
/*=================骑士周游算法分析--用双向链表实现===============*//*
注 意 ： 此 算 法 需 已 经 在 tubor c++中 通 过 ， 但 在 vc++有 些 问 题 ， 主 要 在 struct stack*head=(struct stack*)malloc(LEN);struct stack*q=head ;这 两 条 语 句 的 定 义 上 算 法 分 析 ： 此 算 法 主 要 用 双 向 链 表 来 存 储 和 删 除 位 置 元 素 ， 其 他 部 分 与 数 组 实 现 的 算 法 一 样 ， 不 再 赘 述 。 */
#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct stack)
//定义一个结构变量
struct stack {
int row ;
int col ;
int dir ;
struct stack*next ;
struct stack*prior ;
};
struct stack*head=(struct stack*)malloc(LEN);
//定义一个头指针，使得能形成整个链表
struct stack*q=head ;
//定义一个指向结构体的指针，总是用来指向当前结点
//压栈操作，每压一个，连入双向链表中
void push(int i,int j,int v){
struct stack*p=(struct stack*)malloc(LEN);
p->row=i ;
p->col=j ;
p->dir=v ;
q->next=p ;
p->prior=q ;
q=p ;
}
//出栈操作，清空当前元素
void pop(){
struct stack*temp ;
temp=q->prior ;
free(q);
q=temp ;
}
void start(){
int y,z,v=0 ;
int i,j ;
int move[8][2]= { 2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1 };
int c[6][6];
for(i=0;i<6;i++){
for(j=0;j<6;j++)
c[j]=0 ;
}
printf("input y:");
scanf("%d",&y);
printf("input z:");
scanf("%d",&z);
int account=0 ;
while(account<35) {
while(v<8) {
i=y+move[v][0];
j=z+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0) {
push(y,z,v+1);
account++;
c[y][z]=account ;
y=i ;
z=j ;
v=0 ;
}
else v++;
}
if(v==8&&account>0&&account!=35) {
y=q->row ;
z=q->col ;
v=q->dir ;
pop();
c[y][z]=0 ;
account--;
}
}
c[y][z]=36 ;
for(i=0;i<6;i++){
for(j=0;j<6;j++){
printf("%4d",c[j]);
}
printf("\n");
}
}
void main(){
printf("\n");
start();
}
/*程 序 运 行 结 果 ：
input y :1
input z :2
36 21 12 27 30 19
11 26 1 20 13 28
22 35 14 29 18 31
25 10 23 2 7 4
34 15 8 5 32 17
9 24 33 16 3 6
input y :3
input z :2
26 21 12 35 32 19
11 36 25 20 13 34
24 27 22 33 18 31
7 10 1 16 3 14
28 23 8 5 30 17
9 6 29 2 15 4*/
36、背包问题
/* 0/1背包问题的回溯法算法*/
#include<stdio.h>
#define n 4
double m=15;
double w[]={2,4,6,9};
double p[]={10,10,12,18};
int x[n];
int x1[n];
double max=0;
double totalweight=0;
void solve(int i){
if(i==n){
int i;double sum;
for(sum=0,i=0;i<n;i++)
sum+=x1[i]*p[i];
if(sum>max){
max=sum;
for(i=0;i<n;i++)
x[i]=x1[i];
}
return;
}
x1[i]=0;/* 将x[i]置为0 */
solve(i+1);
if(totalweight+w[i]<=m){
x1[i]=1;/* 将x[i]置为1 */
totalweight+=w[i];
solve(i+1);
totalweight-=w[i];
}
}
int main(){
int i;
solve(0);
for(i=0;i<n;i++)
printf("x%d=%d ",i+1,x[i]);
return 0;
}
/* 0/1背包问题的动态规划法算法*/
#include<stdio.h>
#include<stdlib.h>
#define ymax 100
#define nmax 100
float f[nmax][ymax];
void Knapsack(float p[],int w[],int c,int n)
{
int y=0,i=0;
for(y=0;y<ymax;y++)
f[n][y]=0;
for(y=w[n];y<=c;y++)
f[n][y]=p[n];
for(i=n-1;i>1;i--)
{
for(y=0;y<ymax;y++)
f[i][y]=f[i+1][y];
for(y=w[i];y<=c;y++)
f[i][y]=(f[i+1][y]>(f[i+1][y-w[i]]+p[i]))?f[i+1][y]:(f[i+1][y-w[i]]+p[i]);
}
f[1][c]=f[2][c];
if(c>=w[1])
f[1][c]=(f[1][c]>(f[2][c-w[1]]+p[1]))?f[1][c]:(f[2][c-w[1]]+p[1]);
}
void traceback(int w[],int c,int n,int x[])
{
int i=0;
for(i=1;i<n;i++)
if(f[i][c]==f[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
x[n]=f[n][c]?1:0;
}
int main()
{
float s=0,temp=0; float *p;
int m=0,n=0,i=0,*w,*x;
printf("please input the maximum weight of the bag:\nm=");
scanf("%d",&m);
printf("please input the number of objects:\nn=");
scanf("%d",&n);
p=(float*)malloc((n+1)*sizeof(float));
printf("please input the prices of all the objects:\n");
for(i=1;i<=n;i++)
scanf("%f",p+i);
w=(int*)malloc((n+1)*sizeof(int));
printf("please input the weight of all the objects:\n");
for(i=1;i<=n;i++)
scanf("%d",w+i);
x=(int*)malloc((n+1)*sizeof(int));
Knapsack(p,w,m,n);
traceback(w,m,n,x);
s=f[1][m];
printf("the max value is %f\n",s);/*输出*/
for(i=1;i<=n;i++)
{
if(x[i]==1)
{
printf(" the p: %f",p[i]);
printf(" the w: %d\n",w[i]);
}
}
return 0;
}
/* 背包问题的贪心法算法*/
#include<stdio.h>
#include<stdlib.h>
float knapSack(float* p, float* w, float* x ,float m, int n)
{/* 线性表p和w中,按p[i]/w[i]的降序分别存放物体的价格（单位为元）和重量（单位为公斤）;*/
/* m是背包能放的物体总重量，n是物体件数。x存放解向量*/
int i=0;
float s=0;
for(i=0;i<n;i++)
x[i]=0;
i=0;
while(i<n&&w[i]<m)
{
m-=w[i];
s+=p[i];
x[i] =1;
i++;
}
if (i<n&&m>0)
{
s+=p[i]*m/w[i];
x[i]=m/w[i];
i++;
}
return (s);
}
int main()
{
float m=0,s=0,temp=0; float *p,*w,*x;
int n=0,i=0,flag=1;
printf("please input the maximum weight of the bag:\nm=");
scanf("%f",&m);
printf("please input the number of objects:\nn=");
scanf("%d",&n);
p=(float*)malloc(n*sizeof(float));
printf("please input the prices of all the objects:\n");
for(i=0;i<n;i++)
scanf("%f",p+i);
w=(float*)malloc(n*sizeof(float));
printf("please input the weight of all the objects:\n");
for(i=0;i<n;i++)
scanf("%f",w+i);
/* 线性表p和w中,按p[i]/w[i]的降序分别存放物体的价格（单位为元）和重量（单位为公斤）;*/
while(flag!=0)
{
flag=0;
for(i=0;i<n-1;i++)
{
if(p[i]/w[i] < p[i+1]/w[i+1])
{
temp=p[i];
p[i]=p[i+1];
p[i+1]=temp;
temp=w[i];
w[i]=w[i+1];
w[i+1]=temp;
flag=1;
}
}
}
x=(float*)malloc(n*sizeof(float));
s=knapSack(p,w,x,m,n);
printf("the max value is %f\n",s);/*输出*/
for(i=0;i<n;i++)
{
if(x[i]>0)
{
printf("the x: %f",x[i]);
printf(" the p: %f",p[i]);
printf(" the w: %f\n",w[i]);
}
}
return 0;
}
/* 简化背包问题的非递归算法*/
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 20
#define TRUE 1
#define FALSE 0
int* w;
struct NodeBag /* 栈中元素的定义 */
{
int s , n ;
int r ; /* r的值为1,2,3 */
int k;
};
typedef struct NodeBag DataType;
struct SeqStack /* 顺序栈类型定义 */
{
DataType s[MAXNUM];
int t; /* 指示栈顶位置 */
};
typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */
PSeqStack createEmptyStack_seq( void )
{ PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack==NULL)
printf("Out of space!! \n");
else
pastack->t=-1;
return (pastack);
}
void push_seq( PSeqStack pastack, DataType x )
/* 在栈中压入一元素x */
{
if( pastack->t >= MAXNUM - 1 )
printf( "Overflow! \n" );
else
{ pastack->t = pastack->t + 1;
pastack->s[pastack->t] = x;
}
}
void pop_seq( PSeqStack pastack )
/* 删除栈顶元素 */
{
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t = pastack->t - 1;
}
DataType top_seq( PSeqStack pastack )
/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
{
return (pastack->s[pastack->t]);
}
int nknap(int s,int n)
{
struct NodeBag x;
PSeqStack st;
int k;
st = createEmptyStack_seq( ); /* entry0: 初始调用入口 */
x.s = s; x.n = n; x.r = 1;
push_seq(st,x);
entry1: /* 递归调用入口 */
x = top_seq(st);
pop_seq(st); /* 该函数与后面最接近的一个push_seq函数对是为了完成修改栈顶元素 */
if (x.s == 0)
{
x.k = TRUE;
push_seq(st,x);
goto exit2;
}
else if (x.s<0 || (x.s>0 && x.n<1))
{
x.k = FALSE;
push_seq(st,x);
goto exit2;
}
else
{
push_seq(st,x); /* 由于此处需要进一步往下递归，所以需再次入栈 */
x.s = x.s - w[x.n-1];
x.n = x.n - 1;
x.r = 2;
push_seq(st,x);
goto entry1;
} exit2: /* 返回处理 */
x = top_seq(st);
pop_seq(st);
switch (x.r)
{
case 1: free(st);
return(x.k);
case 2: goto L3;
case 3: goto L4;
} L3: /* 继续处理1 */
if (x.k == TRUE)
{
x = top_seq(st);
pop_seq(st);
x.k = TRUE;
push_seq(st,x);
printf("result n=%d , w=%d \n",x.n,w[x.n-1]);
goto exit2;
}
else
{
x = top_seq(st);
x.s = x.s;
x.n = x.n - 1;
x.r = 3;
push_seq(st,x);
goto entry1;
} L4: /* 继续处理2 */
k = x.k;
x = top_seq(st);
pop_seq(st);
x.k = k;
push_seq(st,x);
goto exit2;
}
int main()
{
int s=0,n=0,result=0,i=0;
printf("please input s=");/*输入s*/
scanf("%d",&s);
printf("please input n=");/*输入n*/
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("please input the %d numbers(weight):\n",n);/*输入重量*/
for(i=0;i<n;i++)
scanf("%d",w+i);
result=nknap(s,n);
if(result==0)
printf("no solution!\n");
return 0;
}
/* 简化背包问题的递归算法*/
#include<stdio.h>
#include<stdlib.h>
int knap(int s,int n);
int* w;
int knap(int s,int n)
{
if ( s == 0 )
return (1);
else if ((s<0)||((s>0)&&(n<1)))
return(0);
else if ( knap(s - w[n-1],n - 1)==1 )
{
printf("result: n=%d ,w[%d]=%d \n",n,n-1,w[n-1]);
return (1);
}
else
return ( knap(s,n - 1) );
}
int main()
{
int s=0,n=0,result=0,i=0;
printf("please input s=");/*输入s*/
scanf("%d",&s);
printf("please input n=");/*输入n*/
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("please input the %d numbers(weight):\n",n);/*输入重量*/
for(i=0;i<n;i++)
scanf("%d",w+i);
result=knap(s,n);
if(result==0)
printf("no solution!\n");
return 0;
}
|