C 语言练习程序小结 一

作者 Marlous 日期 2018-08-01
数据结构与算法
C 语言练习程序小结 一

小结一 某点与圆

  • 需要用多个数学函数求值时，类型最好用 double。
  • 非整型求绝对值用 fabs() 函数，而不是 abs()。
  • 二次方用 pow() 函数，而不是习惯性用 ^2。

例：四个圆塔高10米，半径1米，圆心在四个象限绝对值为（2，2），判断任意点坐标所在处高度？

解：某一点到圆心的距离大于圆的半径。
在圆外即满足 (2-|y|)^2 + (2-|x|)^2 > 1 。

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<math.h>
int main()
{
    double x,y;
    double r;
    printf("Enter site x,y value:\n");
    printf("x=?\n");
    scanf("%lf",&x);printf("x value:%lf\n",x);
    printf("y=?\n");
    scanf("%lf",&y);printf("y value:%lf\n",y);
    r=pow((2-fabs(y)),2)+pow((2-fabs(x)),2);
    r=sqrt(r);
    printf("\nr=%lf\n",r);
    if(pow((2-fabs(y)),2)+pow((2-fabs(x)),2)>1) //即 r>1
    {
        printf("\nHeight:0 M\n");
    }
    else
    {
        printf("\nHeight:10 M\n");
    }
    return 0;
}

程序运行结果：
意点坐标所在处高度

小结二 求根

  • 迭代法求平方根。公式为 x2=(x1+a/x1)/2 ，x1 初值取任意值 (1)。
  • 牛顿迭代法求方程的根。公式为 x2=x1-f(x1)/f'(x1) ，x1 初值取某数附近。
  • 二分法求方程的根。公式为取区间中点 i=(a+b)/2 ，判断 f(a)*f(i)<0 是区间改为 [a,i]，否则区间就在 [i,b] 。

1 迭代法求平方根

例：求 x=a^(1/2) ？

解：求平方根的迭代公式为 x2=(x1+a/x1)/2,x2 下标为 n+1，x1 下标为 n。
利用迭代公式，使两次值的差的绝对值小于 1e-5，注意初值可以取任意值，本例取 1。

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
#include<math.h>
int main()
{
    double a,x1,x2,temp,num1,num2;
    x1=1;//x1取一个初值。
    scanf("%lf",&a);
    do
    {
        x2=0.5*(x1+a/x1);//迭代公式。
        temp=x1;//保存求出的x1值。
        x1=x2;//准备下一次循环x1的值。

        num1=temp-x2;
        num2=fabs(num1);
    }while(num2>=10e-5);//满足一直循环。
    printf("%lf is root1=%lf,root2=%lf\n",a,temp,x2);
    return 0;
}

程序运行结果：
迭代法求平方根

2 牛顿迭代法求方程的根

例：2x^3 - 4x^2 +3x - 6 = 0，求 1.5 附近的根？

解：公式为 x2=x1-f(x1)/f'(x1)，x2 下标为 n+1，x1 下标为 n。
利用迭代公式，使两次值的差的绝对值小于 1e-5，注意初值取 1.5。

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<math.h>
int main()
{
    double x1,x2,temp,num;
    x1=1.5;
    do
    {
        x2=x1-(2*pow(x1,3)-4*pow(x1,2)+3*x1-6)/(6*pow(x1,2)-8*x1+3);
        temp=x1;
        x1=x2;
        num=fabs(temp-x2);
    }while(num>1e-5);
    printf("2x^3 - 4x^2 +3x - 6 = 0 root at 1.5\n\nroot1=%lf\nroot2=%lf\nroot=%5.2lf\n",temp,x2,x2);
    return 0;
}

程序运行结果：
牛顿迭代法求方程的根

3 二分法求方程的根

例：求 2x^3 - 4x^2 + 3x - 6 = 0 在（-10，10）之间的根？

解：取区间中点 i=(a+b)/2，如果 f(a)*f(i) 小于 0，则区间就变为在 [a,i]，否则区间就在 [i,b]，将新的区间表示为 [a,b]

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<math.h>
int main()
{
    double a=-10,b=10,i,s;
    do
    {
        i=(a+b)/2;
        s=(2*pow(a,3)-4*pow(a,2)+3*a-6)*(2*pow(i,3)-4*pow(i,2)+3*i-6);
        if(s<0)
        {
            b=i;
        }
        else
        {
            a=i;
        }
    }while(b-a>1e-5);
    printf("2x^3 - 4x^2 + 3x - 6 = 0 at(-10,10)\nroot1=%lf,root2=%lf\nroot=%5.2lf\n",a,b,b);
    return 0;
}

程序运行结果：
二分法求方程的根

小结三 复杂问题分解思路

  1. 把类矩阵问题转化成二维平面问题。
  2. 分解为行，列这两个问题。
  3. 其中每行中的列可分解为不同的几个部分。用第二层循环控制列中重复的特征（往往行的特征会影响到列）。

例：输出如图的图形（程序运行结果）。
如图的图形

解：按图形分析出有几行，几列；每一列由什么组成；行列之间的关系（规律）。
图形上半部分，共 8 行，奇数行输出图形偶数行为空行，n 为上半部分图形空格初值。
图形下半部分，共 5 行，奇数行输出图形偶数行为空行，m 为下半部分图形空格初值。如表：

行 i 每一行中空格数 每一行中星号数
第 1 行 3 空格 1 个 *
第 3 行 2 空格 3 个 *
第 5 行 1 空格 5 个 *
第 7 行 0 空格 7 个 *
行 i 每一行中空格数 每一行中星号数
第 1 行 1 空格 5 个 *
第 3 行 2 空格 3 个 *
第 5 行 3 空格 1 个 *

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
int main()
{
    int i,j,n=3,m=1; //n 为上半部分图形空格初值，m 为下半部分图形空格初值。
    for(i=1;i<=8;i++) //图形上面一半行数。
    {
        if(i%2!=0) //判断为奇数行。
        {
            for(j=0;j<=n-1;j++) //每个不同奇数行空格数控制。
            {
                printf(" "); //每行输出空格数。
            }
            n=n-1; //下一个奇数行空格数减一。
            for(j=1;j<=i;j++) //每个不同奇数行星号数控制。
            {
                printf("*");
            }
            printf("\n"); //每个奇数行输出后换行。
        }
        else
        {
            printf("\n"); //输出空行。
        }
    }


    for(i=1;i<=5;i++) //图形下面一半行数。
    {
        if(i%2!=0) //判断为奇数行。
        {
            for(j=1;j<=m;j++) //每个不同奇数行空格数控制。
            {
                printf(" "); //每行输出空格数。
            }
            m=m+1; //下一个奇数行空格数加一。
            for(j=1;j<=6-i;j++) //每个不同奇数行星号数控制。
            {
                printf("*");
            }
            if(i!=5) //确保最后一行不换行。
            {
                printf("\n");
            }
        }
        else
        {
            printf("\n"); //输出空行。
        }
    }
    return 0;
}

小结四 关于素数问题

  • 通用求素数方法：无法被去掉一和它本身范围内整数整除。（最小素数为 2，这里从 3 开始讨论）
  • 筛选法求素数：用数 i 后面所有的数（循环 i+1 到某个上限）除以 i，能整除的去掉。

1 通用求素数方法

例：输出一百以内的素数？

解：判断的数是否能被范围为 [2，需判断的数-1] 整数整除，没有则为素数。

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
int main()
{
    int i,j;
    for(i=100;i<=200;i++)
    {
        int flag=0; //先默认是素数。
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                flag=1; //只要有一个能被整除说明不是素数，标记为1。
            }
        }
        if(flag!=1)
        {
            printf("number is %d\n",i);
        }
    }
    return 0;
}

程序运行结果：
通用求素数方法

2 筛选法求素数

例：筛选法求一百之内的素数？

解：先把 N 个自然数按次序排列起来。1 不是质数，也不是合数，要划去。
第二个数 2 是质数留下来，而把 2 后面所有能被 2 整除的数都划去。
2 后面第一个没划去的数是 3，把 3 留下，再把 3 后面所有能被 3 整除的数都划去。
3 后面第一个没划去的数是 5，把 5 留下，再把 5 后面所有能被 5 整除的数都划去。
这样一直做下去，就会把不超过 N 的全部合数都筛掉，留下的就是不超过 N 的全部质数。

用一个数组标记哪些不是素数，1 标记为是，0 标记为不是；
默认全是素数，对 0，1，2 对应的直接判断赋值；
从最小素数 2 开始，用它后面的所有数（循环实现）来除以它，判断能整除的标记为 0；
输出标记是的（数组下标）。

即用数 i 后面所有的数（循环 i+1 到某个上限）除以 i，能整除的去掉。

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
int main()
{
    int num[101];
    int i,j;
    num[0]=0; //用数组来标记一个数是否是素数。
    num[1]=0;
    num[2]=1;
    for(i=3;i<=100;i++)
    {
        num[i]=1; //初始默认为1，即默认为素数。
    }
    for(i=0;i<=100;i++)
    {
        if(num[i]!=0) //从标记为素数的2开始符合条件。
        {
            printf("%d ",i);
            for(j=i+1;j<=100;j++) //从i后面的数开始去除以i，把能整除的去掉（标记置为0）。
            {                     //下一个循环是最接近i的没被去掉的数。
                if(num[j]==0)
                {
                    //跳过已经被标记过的。
                }
                else
                {
                    if((j%i==0)) //大于i的数除以i。能整除则不是素数。
                    {
                        num[j]=0;
                    }
                }
            }
        }
    }
    return 0;
}

程序运行结果：
筛选法求素数

小结五 一个数的因子

假如整数n除以m，结果是无余数的整数，那么我们称m就是n的因子。
因子就是所有可以整除这个数的数,不包括这个数自身,因数包括本身。

例：找出一千内的所有完数（一个数等于它的所有因子之和）？

解：一个数一个数的判断，对每个数找出它的因子并累加，判断是否符合条件，符合则是完数。

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
void PrintNumber(int a);
int main()
{
    int i,j,s;
    for(i=2;i<=1000;i++)
    {
        s=0;
        for(j=1;j<i;j++)//判断数i的因子。
        {
            if(i%j==0)
            {
                s=s+j;//数i的因子之和。因子为j。
            }
        }
        if(i==s)
        {
            PrintNumber(i);
        }
    }
    return 0;
}

void PrintNumber(int a)
{
    int n;
    printf("%d its factors are ",a);
    for(n=1;n<a;n++)
    {
        if(a%n==0)
        {
            printf("%d,",n);
        }
    }
    printf("\n");

}

程序运行结果：
一个数的因子

FEATURED TAGS
数据结构与算法