博文
牛顿法求平方根和立方根(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)
求最大公约数的两种算法(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;
......
stu(1147)Z(2005-08-23 18:46:00)
摘要：#include<stdio.h>
int main()
{
char c;
int i;
int t;
for(c=getchar();c!=-1;c=getchar())
{
if(c=='%'){
scanf("%d",&t);
for(i=0;i<t;i++) printf(" ");
}
else if(c=='#'){
scanf("%d",&t);
for(i=0;i<t;i++) printf("\n");
}
......
pku(2000)(2005-08-23 02:10:00)
摘要：#include <stdio.h>
int main()
{
int days;
int i=1;
int pos;
long money;
while(scanf("%d",&days))
{
pos=1;
i=0;
money=0;
if(days==0) return 0;
while(1)
{
if(days>i)
{
money+=pos*pos;
i+=pos;
/* printf("%d-%d-%d-%d ",days,i,money,pos); */
pos=pos+1;
}
else
{
money-=(i-days)*(pos-1);
break;
}
}
......
test(2159)(2005-08-23 01:23:00)
摘要： #include <stdio.h>
#include <string.h>
int main()
{
char a[100],b[100];
int c[26],d[26];
int i,j,k;
int flag=0;
scanf("%s%s",a,b);
for(j=1;j<=25;j++)
{
for(i=0;i<26;i++)
c[i]=d[i]=0;
for(i=0;i<strlen(a);i++)
{
if(a[i]-'A'>=j)
a[i]-=j;
else
a[i]+=26-j ;
/* if(a[i]=='A') */
/* a[i]='Z'; */
/* c[25]++; */
/* else */
/* c[a[i]-'B']++; */
}
for(i=0;i<strlen(a);i++)
d[b[i]-'A']++;
for(i=0;i<26;i++)
{
if(c[i]!=d[i])
{
flag=1;
&......
pku(2196)(2005-08-23 00:40:00)
摘要：#include <stdio.h>
int main()
{
int i;
int a,b,c;
int sum;
for(i=2992;i<10000;i++)
{
a=b=c=0;
sum=i;
a+=sum/1000;
sum=sum%1000;
a+=sum/100;
sum=sum%100;
a+=sum/10;
sum=sum%10;
a+=sum;
sum=i;
b+=sum/1728;
sum=sum%1728;
b+=sum/144;
sum=sum%144;
b+=sum/12;
sum=sum%12;
b+=sum;
sum=i;
c+=sum/4096;
sum=sum%4096;
c+=sum/256;
sum=sum%256;
pku(2136)没有通过(2005-08-23 00:27:00)
摘要：#include<iostream.h>
#include <stdio.h>
#include <string.h>
int b[26];
int main()
{
char a[72];
int i,j;
int max=0,max2;
for(i=0;i<26;i++)
b[i]=0;
for(i=0;i<=4;i++)
{
cin.getline(a,72);
for(j=0;j<strlen(a);i++)
if(a[j]>='A' && a[j]<='Z')
b[a[j]-'A']++;
}
for(i=0;i<26;i++)
if(b[i]>max)
max=b[i];
for(i=0;i<max;i++)
{
for(j=25;j>=0;j++)
if(b[j]>=max-i)
{
max2=j;
break;
}
for(j=0;j<=max2;j++)
{
if(b[j]>=max-i)
printf("*&q......
pku(2105)(2005-08-22 23:59:00)
摘要：#include<stdio.h>
#include <math.h>
int main()
{
int n,i,num;
int pos;
char a[40];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",a);
num=0;
for(pos=0;pos<=7;pos++)
{
num+=(a[pos]-'0')*(int)pow(2,7-pos);
}
printf("%d.",num);
num=0;
for(pos=0;pos<=7;pos++)
{
num+=(a[pos+8]-'0')*(int)pow(2,7-pos);
}
printf("%d.",num);
num=0;
for(pos=0;pos<=7;pos++)
{
&nbs......
pku(1080)没有通过(2005-08-22 23:36:00)
摘要：#include<stdio.h>
#include <string.h>
char a[100],b[100],c[100];
int max;
int ctoi(char a)
{
if(a=='A')
return 0;
if(a=='C')
return 1;
if(a=='G')
return 2;
if(a=='T')
return 3;
if(a=='-')
return 4;
}
int fun2(char a,char b)
{
int arr[5][5]={
{5,-1,-2,-1,-3},
{-1,5,-3,-2,-4},
{-2,-3,5,-2,-2},
{-1,-2,-2,5,-1},
{-3,-4,-2,-1,0}};
return arr[ctoi(a)][ctoi(b)];
}
int fun(char *s,int n,int l)
{
char s1[100......
字符串中添加n个'-'的所有情况.(2005-08-22 23:07:00)
摘要：#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()
{<......