博文
运筹学之最短路径(2005-11-16 18:33:00)
摘要：#include <iostream.h>#include <fstream.h>#define M 99999int main(){ int G[100][100]; int n; int p[100],flag[100],s[100]; int cur; int m,k,l,i,j; ifstream fin("in.txt"); //enter fin>>n; for(i=0;i<n;i++) for(j=0;j<n;j++) G[i][j]=M; for(i=0;i<n;i++) { fin>>m; for(j=0;j<m;j++) { fin>>k>>l; G[i][k-1]=l; } } for(i=0;i<n;i++) { flag[i]=0; s[i]=M; } cur=0; flag[cur]=1; s[cur]=0; p[cur]=0; for(i=1;i<n;i++) { for(j=0;j<n;j++) { if(flag[j]==0) { m=s[cur]+G[cur][j]; if(m<s[j]) { s[j]=m; p[j]=cur; } &nbs......
递归(2005-08-30 20:43:00)
摘要：递归算法
程序调用自身的编程技巧称为递归（recursion）。
一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，……。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。
反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。
阶乘的算法可以定义成函数
n*f(n－1) (n>0)
f(n)＝
f(n)=1 (n=0)
当n>0时，用f(n-1)来定义f(n)，用f(n-1-1)来定义f(n-1)……，这是对递归形式的描述。
当n=0时，f(n)=1，这是递归结束的条件。
递归算法一般用于解决三类问题：
⑴. 数据的定义形式是按递归定义的。
比如阶乘的定义。
例1 又如裴波那契数列的定义：f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2
对应的递归程序为：
var n:integer;
function f(n:integer):longint;
begin
case n of
0:f:=1; {递归结束条件}
1:f:=2;
else
f:=f(n-1)+f(n-2) ｛递归调用｝
&nb......
背包问题(ZT)(2005-08-26 16:02:00)
摘要：背包问题的递归算法
/*#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......
数划分问题(2005-08-23 19:42:00)
摘要：设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
不取任何东西不可能重量为负:
&......
牛顿法求平方根和立方根(2005-08-23 19:28:00)
摘要：例题：采用牛顿法求平方根
给定一个正数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
&nb......
求最大公约数的两种算法(2005-08-23 19:03:00)
摘要：求最大公约数的两种算法
________________________________________
辗转相除法和移位相减法（Euclid & stein 算法）
给出Stein算法如下：
1. 如果A=0，B是最大公约数，算法结束
2. 如果B=0，A是最大公约数，算法结束
3. 设置A1 = A、B1=B和C1 = 1
4. 如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
5. 如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
6. 如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
7. 如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn
8. n++，转4
//greatest common divisor
//by heaton
//2005/03/11
#include <iostream>
using namespace std;
//交换a ，b的值
void swap(int& a1,int &b1)
{
int temp;
temp=a1;
a1=b1;
b1=temp;
}
//辗转相除法
int gcd(int a,int b)
{
&......