王道C语言

第五周作业答案

什么是递归？使用递归的代码和使用循环的代码哪个性能更好一些？

递归就是在函数定义里面直接或者间接调用本函数
通常使用递归的代码性能会弱于循环的代码，因为函数调用的时候会申请栈帧

使用分治法的基本流程有哪些步骤？如果想好了分治法的算法方案如何写出C代码？

基本流程：
1、找到大问题到小问题的转移方案 --> 递归调用函数
2、找到最小问题的解决方案 --> 直接返回结果

栈溢出有几种可能？分别是什么原因导致的？

栈溢出有两种可能性：
1、单个调用函数当中局部变量太多超过栈帧的限制
2、递归调用的深度太大导致栈溢出

OJ习题C语言学习 | week05_递归求最大公约数

#include<string.h> 
#include<stdio.h>
#include<stdlib.h>

int gcd(int a,int b){
    if(a > b){
        return gcd(a-b,b);
    }
    else if(a < b){
        return gcd(a, b-a);
    }
    else if(a == b){
        return a;
    }
}
int main(){
    int m,n;
    scanf("%d,%d",&m,&n);
    printf("%d\n",gcd(m,n));
    return 0;
}

OJ习题C语言学习 | week05_递归进制转换

#include<string.h> 
#include<stdio.h>
#include<stdlib.h>

void dec2oct(int n){
    if(n >= 8){
        dec2oct(n/8);
        printf("%d", n%8);
    }
    else {
        printf("%d", n);
    }
}
int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        dec2oct(n);
      	printf("\n");
    }
    return 0;
}

OJ习题C语言学习 | week05_吃糖果

#include<string.h> 
#include<stdio.h>
#include<stdlib.h>
int f(int n){
    if(n == 1){
        return 1;
    }
    else if(n == 2){
        return 2;
    }
    else {
        return f(n-1)+f(n-2);
    }
}
int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        printf("%d\n", f(n));
    }
    return 0;
}

OJ习题C语言学习 | week05_直线分平面（提示：在离交点足够远的位置，一条新直线总是可以穿过所有的其他直线）

#include<string.h> 
#include<stdio.h>
#include<stdlib.h>
int f(int n){
    if(n == 1){
        return 2;
    }
    else {
        return f(n-1)+n; 
        //和现有的n-1条线相交
        //每和现有的一条线相交，则多分一块
        //经过最后一条线之后还要再一块
    }
}
int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        printf("%d\n", f(n));
    }
    return 0;
}

OJ习题C语言学习 | week05_折线分平面

#include<string.h> 
#include<stdio.h>
#include<stdlib.h>
int f(int n){
    if(n == 1){
        return 2;
    }
    else {
        return f(n-1)+4*n-3;
        //n-1条折线相当于2n-2条射线
        //当引入第n条折线，先引入第一条射线， 会增加 2n-1个平面
        //再引入第二条射线，再会增加2n-2个平面（因为有一个分出来的平面和之前的连通，故去掉一个）
    }
}
int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        printf("%d\n", f(n));
    }
    return 0;
}

OJ习题C语言学习 | week05_骨牌

#include<string.h> 
#include<stdio.h>
#include<stdlib.h>
int f(int n){
    if(n == 1){
        return 1;
    }
    else if(n == 2){
        return 2;
    }
    else if(n == 3){
        return 4;
    }
    else {
        return f(n-1)+f(n-2)+f(n-3);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n", f(n));
    return 0;
}

第五周作业答案 ​

第五周作业答案