C语言经典题目（十）

46.求第N个斐波拉契数列

斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...
数列从第3项开始，每一项都等于前两项之和

方法（一）利用递归求：

#include<stdio.h>

int Fac(int x)
{
    if (x <= 2)
        return 1;
    else
        return Fac(x - 1) + Fac(x - 2);
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d", Fac(n));
    return 0;
}

递归的方法实现虽然可以计算。但是仔细观察代码，就会发现此代码中存在着大量的冗余计算，并且n越大，冗余的越多，计算的越慢。那么究竟有多慢呢？我们用代码看一下。

#include<stdio.h>
int count = 0;
int Fac(int x)
{
    if (x == 3)
        count++;//计算第三个斐波那契数列被算了多少次。
    if (x <= 2)
        return 1;
    else
        return Fac(x - 1) + Fac(x - 2);
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("第%d个斐波那契数列是：%d\n",n, Fac(n));
    printf("第三个斐波拉契数列被计算了%d次", count);
    return 0;
}

我们在计算第40个斐波那契数列的时候，第三个斐波那契数列被重复算了3900多万次。
当我们需要计算的斐波那契数越大时，计算的时间就会越来越长。
所以计算斐波那契数的时候，不宜用递归求解。

方法（二）利用迭代求：

#include<stdio.h>

int  Fac(int x)
{
    int a = 1;
    int b = 1;
    int c = 1;
    while (x > 2)
    {
        c = a + b;
        b = a;
        a = c;
        x--;
    }
    return c;
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("第%d个斐波那契数列是：%d\n",n, Fac(n));
    return 0;
}

47.递归实现n的k次方

#include<stdio.h>
int Fun(int x,int y)
{
    if (y <= 0)
        return 1;
    else
        return x * Fun(x, y - 1);
}
int main()
{
    int n = 0;
    int k = 0;
    scanf("%d %d", &n,&k);
    printf("%d的%d次方是：%d", n,k, Fun(n,k));
    return 0;
}

48.利用递归计算一个数的每位之和

写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
例如：调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
输入：1729
输出：19

#include<stdio.h>
int DigitSum(int n)
{
    if (n > 9)
        return DigitSum(n / 10) + n % 10;
    else
        return n;
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d", DigitSum(n));
    return 0;
}

49.递归求和

#include<stdio.h>
long long Sum(int n)
{
    if (n==1)
        return 1;
    else
        return n+Sum(n-1);
}
int main ()
{
    int n = 0;
    scanf("%d",&n);
    printf("%lld",Sum(n));
    return 0;
}

50.字符串逆序（递归实现）

编写一个函数 reverse_string(char * str) 递归实现。
实现：将参数字符串中的字符反向排列。
要求：不能使用C函数库中的字符串操作函数

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

int my_strLen(char str[]);//函数声明
void reverse_string(char str[]);//函数声明


int my_strLen(char str[]) {//需要一个求数组长度的函数 自定义一个my_strLen
    if (str[0] == '\0') {//当数组开头为结束标志符\0时 表示数组已经遍历完毕
        return 0;
    }
    return 1 + my_strLen(str + 1);//数组长度等于1 + 以第二个元素开头的数组长度
}
    
//逆序函数
void reverse_string(char str[]) {
    int len = my_strLen(str);//首先求出数组长度 长度-1即为数组内最后一个字符下标
    char tem = *str;//定义一个临时变量储存首字符的内容
    *str = *(str + len - 1);//将最后一个元素赋值给第一个字符，完成第一组逆序
    *(str + len - 1) = '\0';//将\0赋值给最后一个字符，使递归找到最后一个字符
    if (my_strLen(str) > 0) {//如果数组长度不小于0 则一直递归下去
        reverse_string(str + 1);
    }
    *(str + len - 1) = tem;//数组长度小于0，即后半部分已经逆序完毕
}                        //此时将前半部分的值逐个速出即可，就是tem里面存储的值

int main() {
    char str[] = "abcdefg";
    printf("before :%s\n", str);
    reverse_string(str);
    printf("after :%s\n", str);

    system("pause");
    return 0;
}