C语言经典题目（26）

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

#include <stdio.h>
int main(int argc, char *argv[])
{
long f1, f2;
f1 = f2 = 1;
printf("\n输出斐波那契数列20项数据如下:\n");
for (int i = 1; i <= 20; i++)
{
printf("%12ld %12ld", f1, f2);
if (i % 2 == 0) /* 控制输出每行四个数字 */
printf("\n");
f1 = f1 + f2; /* 前两个月加起来赋值给第三个月 */
f2 = f1 + f2; /* 前两个月加起来赋值给第三个月 */
}
printf("\n");
return 0;
}

求最大公约数

①辗转相减法

int gcd(int a,int b)
{        
    while(a != b)
    {
        if(a>b)
        {
            a = a - b;
        }
        else 
        {
            b = b - a;
        }
    }
    return a;
}

②穷举法

int gcd(int x,int y)
{
       int temp = 0;
    for(temp = x ; ; temp-- )
    {
        if(x%temp == 0 && y%temp==0) 
               break; 
       }
    return temp;
}

③辗转相除法

int gcd(int x,int y){
    int rem;
    while(n > 0){
        rem = x % y;
        x = y;
        y = rem;
    }
    return x;            
}

④辗转相除法（递归）

int gcd(int x, int y) {
    if (x%y==0)
        return y;
    else 
    return gcd(y, x%y);
    }

2.枚举求解

知道了如何判断最大公约数，剩下的循环枚举就很简单了。

int main()
{
    int count = 0;
    for (int i = 1; i <= 2020; i++)
    {
        for (int j = 1; j <= 2020; j++)
        {
            if (gcd(i, j) == 1)
                count++;
        }
    }
    printf("%d", count);
    return 0;
}

分解质因数

将一个正整数分解质因数。
例：输入90
输出90=233*5。

#include <stdio.h>
int main()
{
int n, i;
printf("\nplease input a number:\n");
scanf_s("%d", &n);
printf("%d=", n);
for (i = 2; i <= n; i++)
{
while (n != i)
{
if (n%i == 0)
{
printf("%d*", i);
n = n / i;
}
else
break;
}
}
printf("%d", n);
return 0;
}