算法学习四 >> "自顶向下"的设计方法

简述：

　　“自顶向下”的算法设计，就是先概要地设计算法的第一层(顶层)，然后步步深入，逐层细分，逐步细分，逐步求精，直到整个问题可用程序设计语言明确的描述出来为止。

设计步骤：

1.首先对问题进行仔细分析，写出程序的主要过程和任务。
2.把大问题分解为几个子问题。
3.处理子问题，形成单独的模块。

【例题】：一个数如果恰好等于它的因子之和(包括1，但不包括这个数本身)，这个数就称为“完数”。求1000以内的“完数”，并按要求输出。

例如：28的因子为1，2，4，7，14，且28 = 1 + 2 + 4 + 7 + 14，则28是“完数”。
输出格式：
```
28 it's factors are 1,2,4,7,14
```

问题分析：

　　因数的定义：整数a除以整数b(b≠0) 的商正好是整数而没有余数，我们就说b是a的因数（这题有要求不能去本身）。第一步通过问题可知判断一个数是不是“完数”，若是完数则按格式输出。第二部怎么判断是不是完数？则可知要因子相加等于其本身。

自顶向下算法设计：

顶层算法

    for(i = 2; i <= n; i++)
    {
        if(i是完数)
        {
            按格式输出;
        }
    }

判断i是否为完数的算法-----------分解模块1

bool isPerfect(int n, int &flag, int a[])    //判断是否为完数的方法
{
    int s = 1;
    for(int i = 2; i < n; i++)
        if(n%i == 0)        //判断i是否为i的因子
        {
            s += i;            //求因子之和
            a[flag++] = i;    //存储n的因子，为输出算法提供条件
        }
    if(s == n)                //判断因子是否与n本身相等
        return true;
    return false;
}

输出算法----------------------------分解模块二　

void print(int i,int a[], int flag)            //输出函数---------模块二
{
    cout << i << " it's facors are: 1";
    for(int i = 0; i < flag; i++)        //循环打印完数的因子
        cout << "," << a[i];
    cout << "
";
}

在主函数中调用算法模块

int main()
{
    int a[1000];    //定义数组a存储因子
    for(int i = 2; i <= 1000; i++)
    {
        int flag = 0;    //初始化数组下标
        if(isPerfect(i, flag, a))    //调用模块一,判断i是否为完数
            print(i,a,flag);            //调用模块二,打印输出
    }
    return 0;
}

s-code:

#include<iostream>
using namespace std;
bool isPerfect(int n, int &flag, int a[])    //判断是否为完数的方法------模块一
{
    int s = 1;
    for(int i = 2; i < n; i++)
        if(n%i == 0)        //判断i是否为i的因子
        {
            s += i;            //求因子之和
            a[flag++] = i;    //存储n的因子，为输出算法提供条件
        }
    if(s == n)                //判断因子是否与n本身相等
        return true;
    return false;
}
void print(int i,int a[], int flag)            //输出函数---------模块二
{
    cout << i << " it's facors are: 1";
    for(int i = 0; i < flag; i++)        //循环打印完数的因子
        cout << "," << a[i];
    cout << "
";
}
int main()
{
    int a[1000];    //定义数组a存储因子
    for(int i = 2; i <= 1000; i++)
    {
        int flag = 0;    //初始化数组下标
        if(isPerfect(i, flag, a))    //调用模块一,判断i是否为完数
            print(i,a,flag);            //调用模块二,打印输出
    }
    return 0;
}

output:

总结：

　　　自顶向下设计的特点：先整体后局部，先抽象后具体(培养模块化思想)。。。。。。。。

算法学习 四 >> "自顶向下"的设计方法

算法学习四 >> "自顶向下"的设计方法