第48题  把一个正整数分解为连续整数之和

在本题程序MODI1.C中,函数fun通过形参n接收一个正的整型值,把n分解为两个以上连续正整数之和,分解方式可能有多种,函数返回分解方式的种数。

例如:若n为501,则共有3种分解方式:

501 = 81 + 82 + 83 + 84 + 85 + 86

501 = 166 + 167 + 168

501 = 250 + 251

请改正程序中的错误,使之得出正确结果。                                                                注意:不许改动 main函数,不许增行或删行,也不许更改程序结构。

MODI1.C:

MODI48-01

参考答案:

MODI48-02

运行结果:

MODI48-03

程序解析:

#include <stdio.h>

文件包含预处理指令#include <stdio.h>支持标准库函数printf、scanf的正常调用。程序要调用某个库函数,就必须包含与之对应的头文件。预处理指令通常位于源文件开头处,单独占一行,行尾无标点。

程序从函数main开始执行。声明:

int n;

定义整型变量n,分配存储,不作初始化,用于读取整数、充当调用函数fun的实参和接收fun的返回值。凡未经初始化的变量,其初值无意义,仅反映新分配内存的当前随机性物理状态。至此,当前存储状态如下图所示,变量的无意义垃圾值以空白表示。

MODI48-04

在函数main中,首先执行下列语句:

printf(″请输入一个整数:″);
scanf(″%d″, &n);

printf语句在标准输出设备(通常是显示器)给出提示信息。scanf语句从标准输入设备(通常是键盘)读取一个正整数于变量n,这里scanf的实参必须是指向变量n的整型指针&n,&是取地址运算符。至此,当前存储状态如下图所示:

MODI48-05

接着,执行下面函数调用语句:

n = fun(n);

以变量n为实参调用函数fun,于是,main的执行被挂起(暂停),fun开始执行。首先,为形参变量n分配存储,完成参数传递:将main中的变量n的值复制于fun的形参n。

在函数fun中,声明:

int j, b, c, m, cnt = 0;

定义整型变量 j、b、c、m,分配存储,不作初始化,辅助完成对n的分解;定义整型变量cnt,分配存储,初始化为0,用于累计分解种数。至此,当前存储状态如下图所示。形参n也是fun的局部变量。这时有两个变量n,同名同型,但不会冲突,因为它们分属不同的函数fun和main、分别存在于不同的存储空间、各有自己的作用域。局部变量只能在自己的作用域中访问。

MODI48-06

在函数fun中,首先执行下面语句,完成分解:

for (b = 1; b <= n/2; b++) {
­      m = n;
­      c = b;
­      while (m >= c) {
­            m −= c; c++;
­      }
­      if (m == 0) {
­            printf(″%d = ″, n);
­            for (j = b; j < c−1; j++)
­                  printf(″%d + ″, j);
­            printf(″%d\n″, j);
­            cnt++;
­      }
}

以n=15为例,分析外层for循环。15有3种分解方式:

15 = 1 + 2 + 3 + 4 + 5

15 = 4 + 5 + 6

15 = 7 + 8

观察发现,由1,2,3,4,5,6,7(n/2)开头的连续整数之和均有可能满足要求,而其它整数开头的均可排除,因为7+8=15,而8+9,9+10,…均大于15,所以n/2是b的取值上限。外层for循环以变量b依次取值1,2,3,4,5,6,7(n/2),穷尽所有可能,在循环体内,逐一辨别,把正确的分解方式挑选出来并计数。下面分析循环体的工作。首先执行下列两条赋值语句:

m = n;
c = b;

将被分解整数n暂存于变量m,将当前开头整数b暂存于变量c,为下面判别以b开头的连续整数之和是否正确分解做好准备。接着执行下面while循环语句:

while (m >= c) {
­      m −= c; c++;
}

从m减去c,再令c加1生成下一个待减整数,如此反复,直到m >= c为假。例如:循环开始前,m为15,c为4。循环3次后,即从15依次减去4,5,6后m变成0,这时c变成7,循环因条件m>=c(0>=7)为假而终止。再例如:循环开始前,m为15,c为6。循环2次后,即从15依次减去6,7后m变成2,这时c变成8,循环因条件m>=c(2>=8)为假而终止。 因此,当while循环终止后,必定出现两种情况之一:m==0 或 m!=0。若m==0为真,则表明发现一种正确分解方式,因此执行下面语句:

­      if (m == 0) {
­            printf(″%d = ″, n);
­            for (j = b; j < c−1; j++)
­                  printf(″%d + ″, j);
­            printf(″%d\n″, j);
­            cnt++;
­      }

将正确的分解方式输出,并累计于变量cnt。当前发现的正确分解方式为:

n = b + (b+1) + … + (c−2) + (c−1)

例如:n为15,b为4,c从4递增为7的情形:15 = 4 + 5 + 6

内层for语句输出 b + (b+1) + … + (c−2) +,再由printf(″%d\n″, j);输出(c−1),这样输出的格式更漂亮。内层for语句因条件j < c−1为假而终止时,j 一定等于c−1。

当外层for循环终止后,各种可能的分解方式均已尝试,所有正确分解均已输出,cnt值就是分解方式的种数。当n为501时,可同理推演。至此,当前存储状态如下图所示:

MODI48-07

接着,执行下面语句:

return cnt;

将正确分解方式种数cnt的值返回调用者函数main,函数fun执行结束,同时收回其存储空间。至此,当前存储状态如下图所示:

MODI48-08

函数fun返回后,main从挂起点即语句n = fun(n);恢复继续执行,将fun的返回值赋于main中的变量n。至此,当前存储状态如上图所示。

接着,执行下面语句:

if (n == 0)
­      printf(″不能分解\n″);
else
­      printf(″共有%d种分解方式\n″, n);

在标准输出设备(通常是显示器)上,将正确分解方式的种数输出。由于这是main的最后语句,随即函数main执行结束、同时收回其存储空间。

知识点:

① 程序执行是动态过程,语句不断执行,变量值不断变化,同时伴随函数局部变量(含形参变量)的创生与消亡。当函数进入时,局部变量因自动分配存储而创生;当函数返回时,因自动收回存储而消亡。形参变量经参数传递获得初值且有意义,非形参局部变量若未经显式初始化,则其初值无意义,称为垃圾值,仅反映新分配内存的当前随机性物理状态。参数传递发生在函数进入后、函数的语句开始执行前,实参表达式(含变量)的值被复制于形参变量之中,名曰″传值″。不同函数的局部变量可以同名,不会冲突,驻留各自的存储空间,只能被所属函数自己的语句访问,这就是局部变量的作用域。函数通过对形参指针的间接引用可以访问调用者函数内的变量,是函数之间双向通信的重要方式,既能从调用者接收数据,又能向调用者回送计算结果。函数通过非指针形参只能从调用者函数接收数据,通过函数返回值只能向调用者回送计算结果,都只是单向通信。

② / 操作符的意义。两整数相除取整商,例如:15 / 3 得 7。

③ 第1处改错考查:应将n = m;改为m = n;,用m暂存n值,以备分解。

④ 第2处改错考查:应在c++后面添加分号,这是语法规则。C语句要么以分号结尾,要么以右花括号结尾。

⑤ 第3处改错考查: if (m != 0) 改为 if (m == 0),若m为0,则发现一种分解方式。

⑥ 算法思想:

穷尽所有可能,用给定条件进行筛选,这是一种常用算法。

⑦ 要理解循控变量b的初值与终值的确定。

⑧ 要理解循控变量 j 的初值与终值的确定。

练习题:

请结合具体n值,手工分析推演程序的执行过程,以便加深理解。

返回