博文

运筹学之最短路径(2005-11-16 18:33:00)

摘要:#include <iostream.h>
#include <fstream.h>
#define M 99999
int 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];
 &nb......

阅读全文(7622) | 评论:2 | 复制链接

递归(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
 ......

阅读全文(3355) | 评论:0 | 复制链接

背包问题(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){<......

阅读全文(4972) | 评论:0 | 复制链接

数划分问题(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<......

阅读全文(3822) | 评论:0 | 复制链接

牛顿法求平方根和立方根(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)

阅读全文(8012) | 评论:2 | 复制链接

求最大公约数的两种算法(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;
 ......

阅读全文(7322) | 评论:0 | 复制链接