Java教程

算法第一次作业(递归)

本文主要是介绍算法第一次作业(递归),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

A Fibonacci


题目描述
定义一个数列f(i) = f(i-1)+f(i-2), f(0) = 0, f(1) = 1.
求f(n) mod (1e9+7)

输入数据
一个正整数n,n<=1e5

输出数据
f(n) mod (1e9+7)


  1. 标准斐波那契问题,可以递归可以循环;可以数组保存可以直接变量保存

  2. 使用递归会超时

  3. 注意mod(1e9).

为什么是1e9+7?

  1. 1e9+7对int来说非常大,通常1e9代表无穷大
    int数值的范围是-2147483648 到 2147483647,1e10已经超出范围了,所以在计算最小值的操作中,1e9常用来初始化代表无穷大。

  2. 对1e9+7取模的原因
    在一些算法题目中,会遇到这样的情况:
    由于结果可能较大,将结果mod 1e9+7,即mod 1000000007 。
    或者

( a * b ) % c = [ ( a % c ) * ( b % c ) ] % c

而这个c最常见的还是1e9+7。
有时候结果比较大的时候,会对结果进行mod 1e9+7操作。为什么呢?
第一:
1e9+7是一个很大的数,int32位的最大值为2147483647,所以对于int32位来说1000000007足够大。int64位的最大值为2^63-1,对于1000000007来说它的平方不会在int64中溢出所以在大数相乘的时候,因为(a∗b)%c=((a%c)∗(b%c))%c,所以相乘时两边都对1000000007取模,再保存在int64里面不会溢出 ,否则两个非常大的数在ab阶段就溢出了。有点于归一化的意思。
当一个问题只对答案的正确性有要求,而不在乎答案的数值,可能会需要将取值很大的数通过求余变小。
第二:
其次,1e9+7是一个质数,在模素数p的情况下an(a非p的倍数)的循环节长为p,这是减少冲突的一个原因。另一方面模素数p的环是无零因子环,也就是说两个非p倍数的数相乘再模p不会是零(如果是0的话,在多个数连乘的情况下会大大增加冲突概率)。比如说如果所有的结果都是偶数…你模6就只可能出现0, 2, 4这三种情况…但模5还是可以出现2, 4, 1, 3这四(4=5-1)种情况的… hash表如果是用取模的方法也要模一个大质数来减少冲突,出题人也会这样来 希望减少你“蒙对“的概率。

易错总结

  1. 用max比较很大数据时,不能先取模
    取mod的时候,如果题目要求你算最大值,并且说由于答案可能很大,输出结果请对1e9+7取,那你千万不能在max函数更新最大值时就取模,这样很可能会出错。

比如:题目过程中有四个数据

2e9+7,1e9+6,1e9+5,1e9+4

然后算法中你用max求最大值时,如果先模上1e9+7,那你会得到1e9,1e9+6,1e9+5,1e9+4,并且max函数算出的最大值是1e9+6,可是这四个数的最大值应该是2e9 + 7才对

正确做法:在求max的时候不要先取mod,而是都以long long型数据比大小,最后得到最大值是2e9 + 7,再对它取mod,得到结果是1e9 + 7

  1. (a∗b)%c 应该变化为((a%c)∗(b%c))%c,c一般为1e9+7
    如果a和b都是非常大的数的话(a∗b)%c 操作还没轮到对c取模就爆了

  2. 取模加括号
    ————————————————
    版权声明:本文为CSDN博主「葫芦娃的爸爸去哪了」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接


题解:

#include<stdio.h>
int main(){
 long int n[100001],i,N;
 scanf("%d",&N);
 n[0]=0;n[1]=1;
 for(i=2;i<=N;i++){
  n[i]=(n[i-1]+n[i-2])%1000000007;
 }
 printf("%d\n",n[N]);
}

F 楼梯

题目描述
楼梯有n阶,可以一步上一阶、两阶或三阶,问有多少种不同的走法
由于答案很大,mod(1e9+7)输出

输入数据
一个正整数n,代表楼梯的阶数,n<=1000000

输出数据
方案数

样例输入
3
样例输出
4


有n阶(n>3)楼梯时,方案数=f(n-1)+f(n-2)+f(n-3)
即在前面三种情况的所有方案数下再走1、2、3阶楼梯。


题解

#include<stdio.h>
int main(){
 long int n[4],i,N,x;
 scanf("%d",&N);
 n[0]=0;n[1]=1;n[2]=2;n[3]=4;
 if(N<4) x=n[N];
 else
  for(i=4;i<=N;i++){
   x=(n[1]+n[2]+n[3])%1000000007;
   n[1]=n[2];
   n[2]=n[3];
   n[3]=x;
  }//递归
 printf("%d\n",x);
 return 0;
}

C 汉诺塔移动次数

题目描述
  给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。要求:

(1)每次只能移动一个圆盘;

(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序;

任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。

输入数据
输入为一个正整数 n, 表示在 A 柱上放有 2n 个圆盘。
输出数据
输出文件hanoi.out仅一行,包含一个正整数,为完成上述任务所需的最少移动次数 An 。


  1. 找到递归关系 A(n)=2*A(n-1)+2

  2. A(n)的结果可能非常大,远超long long int,所以换python或者Java做吧。java可以用BigInteger类


n=int(input())
a=2
for i in range(1,n):
  a=2*a+2
print(a)

C 最小公倍数和最大公约数

题目描述
  输入二个正整数x0,y0(2≤x0≤100000,2≤y0≤1000000),求出满足下列条件的P、Q的个数。
  条件:1.P、Q是正整数
     2.要求P、Q以xO为最大公约数,以yO为最小公倍数。
  试求,满足条件的所有可能的两个正整数的个数。

输入数据
两个正整数
输出数据
满足条件的所有可能的两个正整数的个数
样例输入
3 60
样例输出
4
样例说明
说明:(不用输出)此时的 P  Q 分别为:
            3 60
            15 12
            12 15
            60  3
所以,满足条件的所有可能的两个正整数的个数共4种


分析:设两个整数为:A=k1x0,B=k2x0;k1、k2是互质正整数(因为x0是最大公约数);k1k2=y0/x0(x0y0=A*B:最小公倍数和最大公约数的关系)

  • 从1到 y 0 / x 0 \sqrt{y0/x0} y0/x0 ​遍历k1,若k2为整数且k1、k2最大公约数为1,则计数器加一。

#include <stdio.h>
#include<math.h>
int gcd(int a,int b){
 	if(b)
  		return gcd(b,a%b);
 	else
  		return a;
}
int main(){
	 int x0,y0,k1,k2,count=0,t;//k1<k2
	 scanf("%d%d",&x0,&y0);
	 if(y0%x0==0){
	  	t=y0/x0;
	 for(k1=1;k1<sqrt(t);k1++){
	    if(t%k1==0){
	    	k2=t/k1;
	    	if(gcd(k2,k1)==1)
	     		count+=2;
   		}  
  	}
 }
 printf("%d",count);
}

E 特殊质数

题目描述
农民约翰的母牛总是生产出最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。
农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说:
7 3 3 1
全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。

7331 被叫做长度 4 的特殊质数。
写一个程序对给定的肋骨的数目 N (1< =N< =8),求出所有的特殊质数。数字1不被看作一个质数。

输入数据
单独的一行包含 N 。
输出数据
按顺序输出长度为 N 的特殊质数,每行一个。
并按大小顺序排列(从小到大).
样例输入
4
样例输出
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393


这题是抄的
总体做法还是比较暴力的。

  • 写一个判断是否为质数的函数
  • 写一个递归搜索前x位都是质数的数

例:对于四位数x3x2x1x0,
首先确定x3只能是2,3,7,5,9,然后选出
x3x2是质数的解,再从中找x3x2x1是质数的情况,以此类推。sum保存当前判断的数。


题解:

#include<stdio.h>
int n,js,ans[100000];
int judge_prime(int x){
    if(x<=1)return -1;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return -1;
    }
    return 1;
}

void dfs(int sum,int x){
    if(x==n){
        printf("%d\n",sum);
        return ;
    }
    for(int i=1;i<=9;i+=2){
        if(judge_prime(sum*10+i)==1){
            dfs(sum*10+i,x+1);
        }
    }
}

int main(){
    scanf("%d",&n);
    dfs(2,1);dfs(3,1);dfs(5,1);dfs(7,1);
    return 0;
}

D 简单背包

题目描述
李老师正准备暑假旅行,他有一个容量为L的行李箱和n个物品(n不超过20),每个物品都有自己的体积,物品可以放入行李箱,但行李箱中物品的总体积不能超过行李箱容量,李老师现在想知道他有多少种携带物品的方案(一个物品都不带也算一种方案)

输入数据
第一行为两个正整数n和L,分别代表物品总数和行李箱容量,n<=20,L<=1e9 接下来一行为n个正整数vi,代表第i个物品的体积,vi<=1e8

输出数据
方案数

样例输入
3 10
2 4 5
样例输出
7


0-1背包,暴力搜索,遍历所有2^n种可能。递归树为完全满二叉树。

  • 现在只在遍历到满二叉树的叶子节点时判断是否能装进背包,似乎可以优化,提前判断,提高效率

题解:

#include<stdio.h>
int count;
void fullbitree(int curV,int curN,int L,int n,int v[]){
 if(curN==n){
    if(curV<=L)
    count++;
    return;
 }
 fullbitree(curV,curN+1,L,n,v);
 fullbitree(curV+v[curN],curN+1,L,n,v);
}
int main(){
    int v[20],L,n;
    scanf("%d%d",&n,&L);
    for(int i=0;i<n;i++)
        scanf("%d",&v[i]);
    count=0;
    fullbitree(0,0,L,n,v);
    printf("%d\n",count);
}

这篇关于算法第一次作业(递归)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!