【趣学C语言和数据结构100例】

问题描述

1. 一个球从 100m 高度自由落下，每次落地后反弹回原高度的一半，再落下，求它在第 10 次时共经过多少米，第 10 次反弹多高。

2. 猴子吃桃问题。猴子第 1 天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第 2 天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10 天早上想再吃时，就只剩一个桃子了。求第 1 天共摘多少个桃子。

3. 迭代法求 x = 根号 a。求平方根的迭代公式为 x(n+1) = 1/2 * (xn + a/xn)

4. 用牛顿迭代法求下面方程在 1.5 附近的根: 2x³ - 4x² + 3x - 6 = 0

5. 用筛选法求 100 之内的素数。

   代码分析

   ==6. 物理公式的规律应用==

   每次落地后反弹回原高度的一半，初始total_m，第一次为total_m *= 0.5，for循环计算n次的，共经过，使用sum来计数。
   

==7. 数学公式的规律应用==
已知结果，找倒推规律，求初始。由后一天 = ( 前一天 / 2 ) -1 可知，==前一天 = ( 后一天 + 1 ) *2==，定义天数day，使用while(day--)，求第一天。
==8. 巴比伦法==
迭代公式为 x(n+1) = 1/2 (xn + a/xn)
初次猜测，x0=a/2，那么，代入公式得到x1
使用while开始代法，令x0=x1,代入公式得到x1
当 ∣xn+1−xn∣∣xn+1​−xn​∣ 小于某个设定的精度（例如 1e−51e−5）时停止迭代。

==9. 牛顿迭代法的求解==
牛顿迭代法 ：x(n+1) = x(n) - f(x(n)) / f'(x(n))
即:

对于本题，方程在 1.5 附近的根: 2x³ - 4x² + 3x - 6 = 0
x0,x1=1.5，f,f1
f(x(n))=2x³ - 4x² + 3x - 6
f'(x(n)) =6x² -8x +3

每次令
x0 = x1;
f = ( ( 2 x0 - 4 ) x0 + 3 ) x0 -6;
f1 = ( 6 x0 - 8 ) * x0 + 3;
x1 = x0 - f / f1;
当 ∣xn+1−xn∣∣xn+1​−xn​∣ 小于某个设定的精度（例如 1e−51e−5）时停止迭代。

==10. 筛选法==
筛选法：又称为筛法。先把以个自然数按次序排列起来。1不是质数，也不是合数，要划去第二个数2是质数留不来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，再把与后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的把5留下，全部合数都筛掉，留下的就是不超过N的全部质数。
具体思路：先初始化数组，初始化为数字本身，如果访问过，则赋值为0。定义两个for循环，第一个访问到100，然后判断为0，则跳过。否则进行，从该数开始，到100，找到该数的倍数，并赋值为0。

代码实现

#include<stdio.h>
#include<math.h>
int main(){
   
//  6.一个球从100m高度自由落下,每次落地后反弹回原高度的一半,再落下,再反弹求它在第10次时共经过多少米，第10次反弹多高。
    double total_m = 100.0,sum = 0.0; 
    for(int i = 0; i < 10; i++)
    {
   
        sum += total_m;
        total_m /= 2;
        sum += total_m;
    } 
    printf("第10次时共经过%f米，第10次反弹%f米",sum,total_m);

//  7.猴子吃桃问题。猴子第1天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。第2天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10天早上想再吃时,就只剩一个桃子了。求第1天共摘多少个桃子。)
    分析：后一天 = ( 前一天 / 2 ) -1  --> 前一天 = ( 后一天 + 1 ) * 2
    int day = 9;
    int prev , cur = 1;
    while( day > 0)
    {
   
        prev = ( cur + 1 ) * 2;
        cur = prev;    
        day--;
    }
    printf("第1天共摘%d个桃子",cur);

//    8.迭代法求x=根号a。求平方根的迭代公式为x(n+1）=1/2 * (xn+a/xn) 
//  分析：牛顿迭代法 ：x(n+1) = x(n) - f(x(n)) / f'(x(n)) https://blog.csdn.net/SanyHo/article/details/106365314
    float a , x0 , x1;
    printf("输入一个正整数a的值：");
    scanf("%f",&a);
    x0 = a / 2;
    x1 = ( x0 + a / x0 ) / 2;
    do
    {
   
        x0 = x1;
        x1 = ( x0 + a / x0 ) / 2;
    } while( fabs ( x0 - x1 ) >= 1e-5 );
    printf("[%.2f]的平方根为[%.5f]\n",a,x1);

//    9.用牛顿迭代法求下面方程在1.5近的根:2x的3次-4x的2次+3x-6=0
    double x0 , x1=1.5,f,f1;
    do
    {
   
        x0 = x1;
        f = ( ( 2 * x0 - 4 ) * x0 + 3 ) *  x0 -6;
        f1 = ( 6 * x0 - 8 ) * x0 + 3;
        x1 = x0 - f / f1;
    } while( fabs ( x1 - x0 ) >= 1e-5 );
    printf("方程在1.5近的根为[%.5f]\n",x1);

//   10.用筛选法求 100 之内的素数。
    int i, j, a[100];
    for (i = 0; i < 100; i++) {
   
        a[i] = i + 1;        // 初始化数组
    }

//    非素数为0 
    for (i = 2; i < 100; i++) {
   
        if (a[i - 1] != 0) {
    
            for (j = i + 1; j < 100; j++) {
   
                if (a[j - 1] % a[i - 1] == 0) {
    
                    a[j - 1] = 0;
                }
            }
        }
    }

//  输出素数
    printf("100 之内的素数: ");
    for (i = 0; i < 100; i++) {
   
        if (a[i] != 0) {
   
            printf("%d ", a[i]);
        }
    }

    printf("\n");
    return 0;
}

总结

本文介绍了五个经典的算法问题及其C语言实现，这些问题包括物理规律、数学规律、迭代法求平方根、牛顿迭代法求方程根以及筛选法求素数。这些问题不仅锻炼了我们的编程技巧，也加深了对算法和数学概念的理解。

物理规律问题（球的反弹）要求我们计算球在第10次落地时经过的总距离和反弹高度。这个问题的解决关键在于理解每次落地后球的高度变化规律，并使用循环累加计算。

数学规律问题（猴子吃桃）要求我们倒推猴子第一天摘了多少个桃子。这个问题的解决需要我们从最后一天开始，逆向思考每天桃子的数量变化。

迭代法求平方根问题展示了如何使用巴比伦方法（也称为海伦方法）来近似计算一个数的平方根。这个问题的解决关键在于理解迭代公式，并在迭代过程中控制精度。

牛顿迭代法求方程根问题要求我们求解一个多项式方程的根。这个问题的解决需要我们应用牛顿迭代公式，结合函数的导数，逐步逼近方程的根。

筛选法求素数问题要求我们找出100以内的所有素数。这个问题的解决需要我们使用埃拉托斯特尼筛法，通过筛选掉所有非素数，留下素数。

这些算法的实现不仅展示了C语言在处理数学问题时的能力，也体现了算法设计的基本思想，如迭代、递归和筛选。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对数据结构和算法的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。同时，这些问题的解决也体现了算法在处理数据时的灵活性和效率，为我们在实际开发中遇到类似问题提供了解决思路。