《java趣味编程100例》（连载）

didimm

内容简介：
        《Java趣味编程100例》讲解了100个各种类型的Java编程趣味题的求解过程，旨在帮助读者培养编程兴趣，拓宽Java编程思维，提高Java编程能力，掌握用程序设计解决实际问题的方法与技巧。本书取材注重趣味性与实用性，内容涵盖了Java编程的基础知识和常用算法，讲解时给出了实例的详细代码及注释。本书附带1张光盘，收录了本书配套多媒体教学视频及实例源文件，可大大方便读者高效、直观地学习本书内容。

　　《Java趣味编程100例》共分11章。第1章介绍了8个常见的变幻多姿的图表；第2章介绍了12个身边的数学问题；第3章介绍了8个趣味整数；第4章介绍了9个趣味素数；第5章介绍了8个趣味方程；第6章介绍了8个趣味分数；第7章介绍了10个逻辑推理；第8章介绍了8个趣味变幻；第9章介绍了9个定理与猜想；第10章介绍了9个趣味游戏；第11章介绍了11个其他趣味问题。

　　《Java趣味编程100例》适合高校、职业技术院校及社会培训学校的学生阅读，也适合Java编程爱好者阅读，还可作为各级程序设计选拔赛和全国青少年信息学奥林匹克竞赛的参考书。
   

didimm

目录
第1章  变幻多姿的图表（  教学视频：69分钟）        1
1.1  金字塔图案        1
1.2  九九乘法表        3
1.3  余弦曲线        5
1.4  奥运五环旗        10
1.5  杨辉三角        12
1.6  国际象棋棋盘        16
1.7  心形图        19
1.8  回型矩阵        22
1.9  小结        26
第2章  身边的数学问题（  教学视频：59分钟）        27
2.1  黑色星期五        27
2.2  个人所得税        29
2.3  存钱问题        34
2.4  赛场统分        35
2.5  肇事车辆        37
2.6  分糖果        39
2.7  天平称物        43
2.8  平分七框梨        48
2.9  一维多项式计算        51
2.10  线性方程求解        55
2.11  非线性方程求解（牛顿迭代法）        62
2.12  非线性方程求解（二分法）        65
2.13  小结        68
第3章  趣味整数（  教学视频：51分钟）        69
3.1  不重复的3位数        69
3.2  水仙花数        71
3.3  完全数        74
3.4  相亲数        76
3.5  黑洞数        78
3.6  勾股数        81
3.7  自守数        84
3.8  3位反序数        86
3.9  小结        87
第4章  趣味素数（  教学视频：61分钟）        88
4.1  素数        88
4.2  孪生素数        91
4.3  金蝉素数        93
4.4  可逆素数        97
4.5  回文素数        101
4.6  平方回文素数        104
4.7  梅森尼数        107
4.8  哥德巴赫猜想        109
4.9  等差素数数列        111
4.10  小结        117
第5章  趣味方程（  教学视频：59分钟）        118
5.1  百鸡百钱        118
5.2  楼梯台阶        120
5.3  换硬币        124
5.4  求s=a+aa+aaa+aa…a的值        128
5.5  鸡兔同笼        130
5.6  巧算年龄        132
5.7  五家共井        133
5.8  三色球问题        136
5.9  小结        139
第6章  趣味分数（  教学视频：63分钟）        140
6.1  最大公约数        140
6.2  最小公倍数        142
6.3  分数比较        148
6.4  分数求和        153
6.5  埃及分数式        154
6.6  计算分数精确值        157
6.7  分数数列        160
6.8  猴子分桃        161
6.9  小结        163
第7章  逻辑推理（  教学视频：63分钟）        164
7.1  斐波那契数列        164
7.2  汉诺塔问题        166
7.3  年龄问题        170
7.4  谁在说谎        171
7.5  幂数列        173
7.6  游客国籍        177
7.7  谁家孩子跑得最慢        181
7.8  猴子爬山        184
7.9  兔子产仔        187
7.10  舍罕王赏麦        190
7.11  小结        192
第8章  趣味变幻（  教学视频：62分钟）        193
8.1  分解质因数        193
8.2  乘式还原        196
8.3  除式还原        200
8.4  幻方        202
8.5  泊松分酒        206
8.6  猜牌术        209
8.7  邮票组合        211
8.8  整数拆分        213
8.9  小结        216
第9章  定理与猜想（  教学视频：64分钟）        217
9.1  四色定理        217
9.2  角谷猜想        220
9.3  Л的近似值（割圆术）        223
9.4  Л的近似值（蒙特卡罗）        226
9.5  回文数        229
9.6  卡布列克常数        232
9.7  剩余定理        237
9.8  尼科彻斯定理        242
9.9  马踏棋盘        245
9.10  小结        250
第10章  趣味游戏（  教学视频：67分钟）        251
10.1  掷骰子        251
10.2  发扑克牌        256
10.3  24点        262
10.4  常胜将军        268
10.5  抢30        271
10.6  10点半        275
10.7  人机猜数        287
10.8  过桥游戏        291
10.9  生命游戏        295
10.10  小结        304
第11章  其他趣味问题（  教学视频：71分钟）        305
11.1  字符串匹配        305
11.2  双色球        310
11.3  金额转换        313
11.4  超长整数加法        321
11.5  尾数前移        324
11.6  高斯八皇后        326
11.7  PK计分        331
11.8  罗马数字        333
11.9  找假币        336
11.10  窃贼问题        340
11.11  三色旗        347
11.12  小结        352

didimm

第2章 身边的数学问题
在我们的身边有许多有趣的数学问题，经常编写程序来解决数学问题可以增强我们的逻辑思维能力，开发我们的智力，同时使我们的生活变得多姿多彩。本章将让你学会如何通过程序设计来解决一些有趣的数学问题。
2.1 黑色星期五
1．问题描述
黑色星期五源于西方的宗教信仰与迷信：耶稣基督死在星期五，而13是不吉利的数字。两者的结合令人相信当天会发生不幸的事情。星期五和数字13都代表着坏运气，两个不幸的个体最后结合成超级不幸的一天。所以，不管哪个月的13日又恰逢星期五就叫“黑色星期五”。找出未来几年哪些天是“黑色星期五”。
2．问题分析
这个问题是一个很经典的逻辑判断的题目。通过问题描述，我们知道“黑色星期五”要满足两个条件，一是当天是13号，二是当天还是星期五。我们可以从起始日期开始，循环判断每天是否同时满足这两个条件就可以了。这个方案很容易想到，但是一年三百多天，一天天判断是不是太慢了，有人也许会说，计算机速度快，很快就能处理完。有没有更好的办法呢，当然有了，其实条件说的很明白啊，条件之一必须满足是13号，那么我们就判断13号是不是星期五不就可以了吗，一年日期是13号的，也就12个月里，每个月一个13日，这样我们判断的日期也就缩小到每个月的13号，一年最多判断12次，比较范围大大缩小。每个月的13号到底是星期几呢？Java中的日期处理类Calendar提供的方法能够很容易地获得。
（1）确定程序框架
通过前面的分析，一年内有几个“黑色星期五”，要分别判断每个月的13号是不是星期五，可以通过循环语句循环12次来实现。如果要找到未来n年内的黑色星期五，外层再用循环语句控制循环n次，这样我们就可以写出程序框架了。代码如下：

while(k {
for (int i = 0; i < 12; i++)
{
if(当前月的13号是星期五)
{
System.out.println("黑色星期五："+当前日期);
}
}
year++; //year代表起始年份
k++;
}

下面我们就需要考虑如何判断每个月13号是星期几。
（2）判断13号是星期几
每个月的13号到底是星期几呢？可以通过Java中的日期处理类Calendar提供的方法来获得。使用Calendar类代表特定的时间，需要首先创建一个Calendar的对象，然后再设定该对象中的年月日参数来完成，最后根据Calendar类对象信息来获得星期几。对应代码如下：

//创建一个代表2012年1月13日的Calendar对象
Calendar cal = Calendar.getInstance(); //创建对象
cal.set(2012, 1, 13); //日期的设置
cal.get(Calendar.DAY_OF_WEEK)-1 //星期的获得
cal.getTime() //日期的获得

我们要判断每个月的13号是不是星期五，所以只要把日期的设置方法set()第二个月份参数用循环变量来代替即可。同理，如果要对其他年份进行设置，也只要把第一个年份参数替换掉即可。
（3）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.GregorianCalendar;
import java.util.Scanner;

public class ch2_1
{
public static void main(String[] args)
{
// TODO Auto-generated method stub
Scanner input=new Scanner(System.in); //获取控制台输入对象
System.out.print("请输入起始年份：");
int year=input.nextInt(); //从键盘接收起始年份
System.out.print("请输入打算输出未来几年：");
int n=input.nextInt(); //从键盘接收打算输出年份
getBlackFri(year,n); //调用得到“黑色星期五”方法

}

//打印未来几年的黑色星期五，判断每个月的13号是否是星期五
public static void getBlackFri(int year,int n)
{
//year为输入的年份，n为未来多少年
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd E"); //日期格式对象
int k=0;
Calendar cal = Calendar.getInstance(); //获得日历对象
while(k {
for (int i = 0; i < 12; i++) //内循环控制月份
{
cal.set(year, i,13); //设置日期
if(5==(cal.get(Calendar.DAY_OF_WEEK)-1)) //判断是否是星期五
{
System.out.println("黑色星期五："+sdf.format(cal. getTime())); //输出格式化日期
}
}
year++; //年份增加
k++;
}
}
}

didimm

2.2 个人所得税
1．问题描述
个人所得税是指国家对个人所得额征收的一种税。个人工资薪金所得采用超额累进税率，纳税人所得越高，课税越重。“高收入者多纳税，低收入者少纳税”是个人所得税的显著特点。现行的9级超额累进个人所得税税率表如表2-1所示。
表2-1 所得税税率表
级数 全月应纳税所得额（减去3500元后的余额） 税率/％
1 不超过500元的部分 5
2 超过500元至2000元的部分 10
3 超过2000元至5000元的部分 15
4 超过5000元至20000元的部分 20
5 超过20000元至40000元的部分 25
续表
级数 全月应纳税所得额（减去3500元后的余额） 税率/％
6 超过40000元至60000元的部分 30
7 超过60000元至80000元的部分 35
8 超过80000元至100000元的部分 40
9 超过100000元的部分 45

目前，上表中“全月应纳税所得额”是从月工资、薪金收入中减去3500元后的余额。试根据上述资料编程计算个人所得税，并根据你的家庭成员的月收入求出每月需要缴纳多少个人所得税。
2．问题分析
这个问题是一个很经典的条件分支应用的题目。假设全月应纳税所得额属于第i级别，那么，应缴纳税款=前i–1级累加税款+当前级别超出部分×当前级别税率。
例如，某人月工资、薪金收入4020元，减去3500元，应纳税所得额为520元，由税率表可知，其中500元税率为5%，另外20元税率为10%，所以此人应缴纳个人所得税：500×5%+20×10%=27元。
当前级别超出部分和当前级别税率根据税率表很容易得到，关键是前i–1级累加税款，我们可以通过计算，把每个级数的前i–1级累加税款先算出来，得到一个升级的税率表，如表2-2所示。
表2-2 升级版所得税税率表
级数 全月应纳税所得额（减去3500元后的余额） 税率/％ 扣除累加数
1 不超过500元的部分 5 0
2 超过500元至2000元的部分 10 25
3 超过2000元至5000元的部分 15 175
4 超过5000元至20000元的部分 20 625
5 超过20000元至40000元的部分 25 3625
6 超过40000元至60000元的部分 30 8625
7 超过60000元至80000元的部分 35 14625
8 超过80000元至100000元的部分 40 21625
9 超过100000元的部分 45 29625

（1）确定程序框架
从表2-2中，我们可以发现，一共有9个级数，也就是9个分支，这样我们就可以写出程序框架了。代码如下：

public class ch2_2
{
public static void main(String[] args)
{
...
if(b <=500)
{
//计算当前级数的税款
}
else if(b <=2000)
{
//计算当前级数的税款
}
else if(b <=5000)
{
//计算当前级数的税款
}
else if(b <=20000)
{
//计算当前级数的税款
}
else if(b <=40000)
{
//计算当前级数的税款
}
else if(b <=60000)
{
//计算当前级数的税款
}
else if(b <=80000)
{
//计算当前级数的税款
}
else if(b <=100000)
{
//计算当前级数的税款
}
else
{
//计算当前级数的税款
}
...
}
}

下面我们就需要计算每个级数的税款。
（2）计算每个级数的税款
根据前面的分析，结合表2-2，可以很容易计算每级的税款。假设应纳税所得额为10000元，由表2-2可知，级数为4，税率20%，扣除累计数625，所以应交税款为：625+(10000–5000)*20%，即：

t=625+(b-5000)*0.2 //b代表应纳税所得额，t代表应交税款

同理可以写出各个级数分支的代码。
（3）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

import java.util.Scanner;
public class ch2_2
{
public static void main(String[] args)
{
System.out.print("请输入个人收入：");
Scanner input=new Scanner(System.in); //获取控制台输入对象
double sr=input.nextDouble();
System.out.println("应交个人所得税："+getTax(sr));//调用计算所得税方法
}
public static double getTax(double sal)
{
double t=0; //t代表应交税款
double b =sal-3500; //b代表应纳税所得额
if(b <=500) //计算级数1的税款
{
t=b*0.05;
return t;
}
else if(b <=2000) //计算级数2的税款
{
t=25+(b-500)*0.1;
return t;
}
else if(b <=5000) //计算级数3的税款
{
t=175+(b-2000)*0.15;
return t;
}
else if(b <=20000) //计算级数4的税款
{
t=625+(b-5000)*0.2;
return t;
}
else if(b <=40000) //计算级数5的税款
{
t=3625+(b-20000)*0.25;
return t;
}
else if(b <=60000) //计算级数6的税款
{
t=8625+(b-40000)*0.3;
return t;
}
else if(b <=80000) //计算级数7的税款
{
t=14625+(b-60000)*0.35;
return t;
}
else if(b <=100000) //计算级数8的税款
{
t=21625+(b-80000)*0.4;
return t;
}
else //计算级数9的税款
{
t=29625+(b-100000)*0.45;
return t;
}
}
}
3．扩展训练
前面的代码，在计算每个级数的税款时，都直接加上一个扣除累计数，扣除累计数是我们写代码前，慢慢计算出来的，这个需要不少时间哟，如果级数的分段数字重新划分或每级的税率修改了，那么又要重新算一遍，是不是很麻烦，我们可以尝试把分级的数据段和税款放到数组里，让程序自己来算。参考代码如下：

import java.util.Scanner;

public class ch2_2_2
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int s;
int sum=0;

//salary存放分级标准
int salary[]={0,500,2000,5000,20000,40000,60000,80000,100000};
//rate存放分级税率
int rate[]={5,10,15,20,25,30,35,40,45};

System.out.print("请输入月收入：");
s=in.nextInt();
s=s-3500; //扣除基数

int index=0; //记录级数
//循环查找，属于哪一级，index记录下标
for(int i=0;i {
if(s {
index=i; //找到后记录下标
break;
}
}

System.out.println("级别："+index);
//循环计算扣除累计数
for(int i=0;i {
sum=sum+(int)((salary[i+1]-salary[i])*rate[i]*0.01);
}
//计算最终税款
sum=sum+(int)((s-salary[index-1])*rate[index-1]*0.01);
System.out.print("交税总额："+sum);
}
}

didimm

2.3 存 钱 问 题
1．问题描述
父亲准备为小龙的四年大学生活一次性储蓄一笔钱，使用整存零取的方式，控制小龙每月月初取1000元准备这个月使用。假设银行整存零取的年息为1.71%，请算出父亲至少需要存入多少钱才行。
2．问题分析
这个问题是一个典型的递推问题，分析存钱和取钱的过程，我们可以采用逆推的方法。4年48个月，每月取1000元，最后一个月正好取完。我们可以采用一个数组存放每个月剩余的钱数，那么最后一个月连本带息为1000，即第48个月数组里的值为1000。
第47个月的存折里钱为：取走的1000元生活费+下个月1000月的本金，即：
1000+第48个月的钱数/(1+0.00171/12)
依次类推可以求出第46、45、……、第1个月的钱数：
第46个月的存折里钱为：1000+第47个月的钱数/(1+0.00171/12)
第45个月的存折里钱为：1000+第46个月的钱数/(1+0.00171/12)
……
第1个月的存折里钱为：1000+第2个月的钱数/(1+0.00171/12)
通过以上的递推就可以求出最初存款的钱数。
（1）确定程序框架
通过前面的分析，我们就可以写出程序框架了。代码如下：

public class ch2_3
{
public static final double MONEYRATE=0.0171;
public static void main(String[] args)
{
...
for(int i=47;i>0;i--)
{
//通过循环逆推出前一个月的剩余存款
}
...
}
}

（2）写出递推公式
通过前面的问题分析，我们很容易得到递推公式，如下：

money[i-1]=1000+money[i]/(1+MONEYRATE/12);

（3）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

public class ch2_3
{
public static final double MONEYRATE=0.0171; //存款利率
public static void main(String[] args)
{
//定义一个长度为48的数组，用来装每个月月初还剩下的存款
double money[]=new double[48];

//最后一个月月初1000元
money[47]=1000;
System.out.printf("48月初的剩余存款数为：%.2fn",money[47]);
//通过循环逆推出前一个月的剩余存款
for(int i=47;i>0;i--)
{
money[i-1]=1000+money[i]/(1+MONEYRATE/12);
System.out.printf("%d月初的剩余存款数为：%.2fn",i,money[i-1]);
}
//算出最初要存入的钱，即第一个剩余存款数
System.out.printf("n最初要存入%.2f元。",money[0]);
}
}
2.4 赛 场 统 分
1．问题描述
在编程竞赛中，有10个评委为参赛的选手打分，分数为0～100分。选手最后得分为：去掉一个最高分和一个最低分后其余8个分数的平均值。请编写一个程序实现。
2．问题分析
这是一个典型的求最大值、最小值问题，为方便数据处理，我们可以把10个评委的打分放到数组里，然后通过循环打擂的原则，把最大值、最小值求出来，同时累加求和，这样一次循环就能实现。
（1）确定程序框架
通过前面的问题描述，我们可以首先循环输入10个分数，然后求出最大值、最小值，最后累加求和，算出平均分。程序的框架如下：

public class ch2_4
{
public static void main(String[] args)
{
...
//循环录入10个人的分数
//通过打擂求出最大值、最小值
//累加求和
//输出结果
}
}

（2）循环录入分数
通过一个循环语句，很容易实现，代码如下：

for(i=0;i<10;i++)
{
System.out.print("请输入第"+(i+1)+"分数：";
Scanner input=new Scanner(System.in);
X[i]=input.nextInt();
}

（3）打擂求最大值、最小值
假设评委打分都是整数，我们可以先用两个变量max、min分别存放最低分0分，最高分100，通过一个循环语句，实现打擂，代码如下：

for(i=0;i<10;i++)
{
if(x>max) max=x[i];
if(x }

（4）累加求和
通过一个循环语句，实现累加求和，代码如下：

for(i=0;i<10;i++)
{
sum=sum+x[i]
}

（5）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

import java.util.Scanner;
public class ch2_4
{
public static void main(String[] args)
{
int i,max,min,sum;
int x[]=new int[10];

max=0; //注意，这里存放最小值0
min=100; //注意，这里存放最大值100
sum=0;
for(i=0;i<10;i++) //循环10次，给10个人打分
{
System.out.print("请输入第"+(i+1)+"分数：";
Scanner input=new Scanner(System.in);
x[i]=input.nextInt(); //键盘接收分数，存入数组

sum=sum+x[i]; //累加求和

//通过打擂方式求最大值、最小值
if(x[i]>max)max=x[i];
if(x[i] }
System.out.println("去掉一个最高分和一个最低分："+max+"、"+min);
System.out.println("平均分："+(sum-max-min)/;
}
}

didimm

2.5 肇 事 车 辆
1．问题描述
有一个卡车司机肇事后想逃跑，但是被三个人看见了其车牌号，但是都没看全，甲说：车牌的前两位是一样的；乙说：车牌的后两位是一样的，但与前两位不一样；丙说：车牌是一个数字的平方，请编写一个程序计算该车牌号是多少（车牌号4位数）。
2．问题分析
这是一个典型的穷举法的问题。根据问题描述，我们可以从1100开始判断是不是一个数字的平方，如果是，就是我们要的车牌号，如果不是，再换下一个数1122试试，依此类推，把可能的情况都试一次。
（1）确定程序框架
通过前面的问题分析，我们可以假设车牌号最前一位为i，最后一位为j，通过循环判断i、j组成的数是不是一个平方数。程序的框架如下：

public class ch2_5
{
public static void main(String[] args)
{
...
//i代表最高位上的数字
for (int i = 1; i <= 9; i++)
{
//j代表最低位上的数字
for (int j = 0; j <= 9; j++)
{
//i、j组成的四位数是不是一个平方数
}

}
}
}

（2）平方数判断
程序的关键在于，i、j组成的数是不是平方数，由问题描述可知，车牌号前两位和后两位都是一样的数字，所以，很容易通过i、j写出这个车牌号：iijj，代码如下：

//i、j组成的四位数
t=i*1000+i*100+j*10+j;

车牌表示出来后，我们可以通过循环判断这个数是不是1的平方、2的平方、……、n的平方。如果是，就找到了。为了缩小比较范围，4位数如果是一个数的平方，那么这个数应该介于1000的平方根与10000的平方根之间。我们可以通过一次循环实现判断，代码如下：

//k的取值根据四位数字开平方得到的大概范围
for (int k = 30; k < 100; k++)
{
if (k == Math.sqrt(t))
{
//车牌号找到了
}
}

（3）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

public class ch2_5
{
public static void main(String[] args)
{
int t;
//i代表最高位上的数字
for (int i = 1; i <= 9; i++)
{
//j代表最低位上的数字
for (int j = 0; j <= 9; j++)
{
if(i!=j) //题目要求，两位不相等
{
//i、j组成的四位数
t=i*1000+i*100+j*10+j;
//k的取值根据四位数字开平方得到的大概范围
for (int k = 30; k < 100; k++)
{
if (k == Math.sqrt(t)) //判断是否是平方数
{
System.out.println("车牌号码："+k * k);
}
}
}
}

}
}
}

didimm

2.6 分 糖 果
1．问题描述
10个小孩围成一圈分糖果，老师分给第1个小孩10块，第2个小孩2块，第3个小孩8块，第4个小孩22块，第5个小孩16块，第6个小孩4块，第7个小孩10块，第8个小孩6块，第9个小孩14块，第10个小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩；糖块数为奇数的人可向老师要一块。问经过这样几次后大家手中的糖的块数一样多？每人各有多少块糖？
2．问题分析
分糖的过程是一个重复的过程。根据分糖的游戏规则，我们不停地重复分糖的步骤，我们可以用一个数组存放每个小孩手中的糖，通过循环修改数组中的数，最终达到都相等为止。
（1）确定程序框架
通过前面的问题分析，我们可以定义一个数组存放10个小孩的糖，如果数组里的值不相等就通过循环修改数组的值，修改完后接着判断是不是有奇数，如果有就加1，然后再判断是否相等，不相等再分，循环反复，直至相等为止。程序的框架如下：

public static void main(String args[])
{
int tang[]={10,2,8,22,16,4,10,6,14,20};
int times=0; //记录分糖果次数

//如果小孩手中的糖果不相等，就继续分糖果
while(isSame(tang)==false)
{
//分糖果
times++; //次数加1
//糖果为奇数的向老师要糖果
}

System.out.println("分糖果次数："+times);
System.out.println("每个人最终的糖果个数："+tang[0]);
}
}

（2）分糖果
由问题描述可知，所有的小孩同时将手中的糖分一半给右边的小孩，为了防止最后一个小孩的糖果个数被覆盖了，我们可以先把最后一个小孩（即第10个小孩）的糖果个数先临时保存下来，然后把第9个小孩的糖果一半加上第10个小孩的糖果一半给第10个小孩，依次，把第8个小孩的糖果一半加上第9个小孩的糖果一半给第9个小孩，……，把第1个小孩的糖果一半加上第2个小孩的糖果一半给第2个小孩，最后把临时保存下来的第10个小孩的糖果个数一半加上第1个小孩的糖果一半给第1个小孩，这样分糖果分了一遍。代码如下：

int m=tang[9]; //防止被覆盖，备份
for(int i=9;i>0;i--) //循环分糖果
{
tang[i]=tang[i]/2+tang[i-1]/2;
}
tang[0]=tang[0]/2+m/2; //最后一个小孩分糖果

（3）糖果为奇数的向老师要糖果
由问题描述可知，糖块数为奇数的人可向老师要一块。这个问题比较简单，我们可以通过循环判断数组中的数字是不是奇数，进而是否加1操作。代码如下：

//糖果为奇数的向老师要糖果
for(int i=0;i<10;i++)
if(tang[i]%2!=0)
tang[i]+=1;

（4）判断每个小孩手中的糖果个数是否相等
由问题描述可知，是否继续分糖的条件是，每个小孩手中的糖果是否一样多。我们可以采用循环比较数组相邻两个数字是否相等，相等则计数器（初始值为0）的个数加1，如果个数全相等，那么计数器的值应该为数组的长度减1。代码如下：

public static boolean isSame(int[] a)
{
int n=0;
boolean b=false; //是否相等，标志
for(int i=0;i {
if(a[i]==a[i+1]) //如果相邻两个数相等，计数器加1
{
n++;
}

if(n==a.length-1) //全部相等判断
b=true;
}
return b;
}

（5）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

public class ch2_6
{
/**
* 判断是否全相等,全相等返回true
*/
public static boolean isSame(int[] a)
{
int n=0;
boolean b=false; //是否相等，标志
for(int i=0;i {
if(a[i]==a[i+1]) //如果相邻两个数相等，计数器加1
{
n++;
}

if(n==a.length-1) //全部相等判断
b=true;
}
return b;
}

/**
* 显示数组的值
*/
public static void show(int[] a)
{
if (a == null) //判断数组是否为空
System.out.println("Array = null");
for (int i = 0; i < a.length; i++) //循环输出数组元素
{
System.out.print(a[i] + " ");
}
System.out.println();
}


public static void main(String args[])
{
int tang[]={10,2,8,22,16,4,10,6,14,20}; //最初小孩手中的糖果个数
int times=0;
boolean b=true;

while(isSame(tang)==false) //判断糖果是否分配好，没有就继续分
{
int m=tang[9]; //防止被覆盖，备份
for(int i=9;i>0;i--) //循环分糖果
{
tang[i]=tang[i]/2+tang[i-1]/2;
}
tang[0]=tang[0]/2+m/2; //最后一个小孩分糖果

//记录分糖果次数
times++;
System.out.print("第" + times+ "次分之后结果： ");
show(tang); //显示结果


//糖果为奇数的向老师要糖果
for(int i=0;i<10;i++)
if(tang[i]%2!=0) //如果为奇数，要一个糖果
tang[i]+=1;
}

System.out.println("分糖果次数："+times);
System.out.println("每个人最终的糖果个数："+tang[0]);
}
}

didimm

2.7 天 平 称 物
1．问题描述
有4个砝码，总重量是40克，砝码的质量是整数，且各不相等。请确定它们的质量，使之能称出1～40克任何整数质量的物体。
2．问题分析
这是问题可以采用穷举的办法来实现。假设4块砝码的重量分别为w1、w2、w3、w4，只要穷举出这样的组合{w1、w2、w3、w4}，其中，w1、w2、w3、w4互不相等，w1+w2+w3+w4=40，那么组合{w1、w2、w3、w4}就可能是该问题的解。如果这个组合可以称出1～40克的任意质量，那么这个组合就是问题的答案。
（1）确定程序框架
通过前面的问题分析，主要要分两个步骤：首先如何穷举出所有的组合{w1、w2、w3、w4}，其中w1、w2、w3、w4互不相等，w1+w2+w3+w4=40。其次，如何判断组合{w1、w2、w3、w4}是否可以称出1～40克的任意质量。为了看得更加清楚，我们可以把称重的结果打印出来。程序的框架如下：

public static void main(String args[])
{
//穷举列出这种组合
//判断当前组合是否可以称出1～40克的任意质量
//打印出称重结果
}

（2）穷举列出各种组合
可以采用多重嵌套的方式实现穷举，为了减少穷举次数，我们可以让内层循环搜索的范围小于外层循环搜索的范围。这样每次得到的组合方式的4个元素都不会相等，同时也不会出现“相同组合，不同排列”的情况。关键代码如下：

for(weight1=1;weight1<=40;weight1++)
for(weight2=weight1+1;weight2<=40-weight1;weight2++)
//注意：内循环起始值为外循环值加1
for(weight3=weight2+1;weight3<=40-weight1-weight2;weight3++)
if((weight4=40-weight1-weight2-weight3)>=weight3)
{
//验证当前组合是否可以称出1～40克的任意质量
}

（3）判断当前组合是否可以称出1～40克的任意质量
接下来的问题就是如何判断组合{w1、w2、w3、w4}是否可以称出1～40克的任意质量。如果将其用数学表达式写出，就是要判断方程：
a1w1+a2w2+a3w3+a4w4=W a1，a2，a3，a4∈–1，0，1
在W=1，2，3，…，40时是否都有解。注意，该方程的解a1、a2、a3、a4只能从中{–1,0,1}取值。假设存在这样一组解{a1, a2, a3, a4}={1, –1, 0, 1}使得方程：
a1w1+a2w2+a3w3+a4w4=7
有解，则有：
1*w1+(–1)*w2+0*w3+1*w4=7
=>w1+w4=W+w2
这样天平的一边放上砝码w1和w4，另一边放上砝码w2和重为7克的物品，这说明砝码{w1、w2、w3、w4}可以称出7克的质量。同理，如果方程：
a1w1+a2w2+a3w3+a4w4=W a1,a2,a3,a4∈–1,0,1
在W=1，2，3，…，40时都有解，那么就说明砝码{w1、w2、w3、w4}组合可以称出1～40克的任意质量。关键代码如下：

Int flag=0; //flag为1代表组合找到了，为0代表组合没找到
for(flag=1,x=1;x<41&&flag==1;x++)
//重物在天平左面，d的各种状态包括：-1：砝码在天平左面；1：砝码在右面；0：不用该砝码
for(flag=0,d1=1;d1>-2;d1--)
for(d2=1;d2>-2&&flag==0;d2--)
for(d3=1;d3>-2&&flag==0;d3--)
for(d4=1;d4>-2&&flag==0;d4--)
if(x==weight1*d1+weight2*d2+weight3*d3+weight4*d4)
flag=1;

（4）打印称重结果
砝码的组合找到之后，下面就通过这个组合把如何称重显示出来，过程分析同第（3）步，关键代码如下：

String left = "",right="";
//a1a2a3a4
for(int i=1;i<=40;i++) //循环40次，打印出每种情况
for(int a1=-1;a1<=1;a1++) //三种状态都循环一遍
for(int a2=-1;a2<=1;a2++)
for(int a3=-1;a3<=1;a3++)
for(int a4=-1;a4<=1;a4++)
{
if(i==a1*w4+a2*w3+a3*w2+a4*w1) //如果相等，打印出结果
{
boolean f=true; //表达式右侧第一项标志
left=i+"";
switch (a1) //根据状态，修改表达式
{
case -1: //状态-1：左侧，修改左侧表达式
left=left+"+"+w4;
break;
case 1: //状态1：右侧，修改右侧表达式
if(f) //如果是右侧第一项，数值前不用加“+”
right=right+w4;
Else //如果不是右侧第一项，数值前加“+”
right=right+"+"+w4;
f=false; //右侧出现过数值，修改f标志位
break;
}
switch (a2) //根据状态，修改表达式
{
case -1: //状态-1：左侧，修改左侧表达式
left=left+"+"+w3;
break;
case 1: //状态1：右侧，修改右侧表达式
if(f) //如果是右侧第一项，数值前不用加“+”
right=right+w3;
else
right=right+"+"+w3;
//如果不是右侧第一项，数值前加“+”
f=false; //右侧出现过数值，修改f标志位
break;
}
switch (a3) //根据状态，修改表达式
{
case -1: //状态-1：左侧，修改左侧表达式
left=left+"+"+w2;
break;
case 1: //状态1：右侧，修改右侧表达式
if(f)
right=right+w2;
else
right=right+"+"+w2;
f=false; //右侧出现过数值，修改f标志位
break;
}
switch (a4) //根据状态，修改表达式
{
case -1: //状态-1：左侧，修改左侧表达式
left=left+"+"+w1;
break;
case 1: //状态1：右侧，修改右侧表达式
if(f)
right=right+w1;
else
right=right+"+"+w1;
f=false; //右侧出现过数值，修改f标志位
break;
}

System.out.println(left+"="+right);
}
left=""; //下次循环，清空
right="";

（5）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

public class ch2_7_3
{

/**
* @param args
*/
public static void main(String[] args)
{
int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag;
int w1=0,w2=0,w3=0,w4=0;
System.out.printf("The weight is broke up as following 4 pieces:");
for(weight1=1;weight1<=40;weight1++) //穷举
for(weight2=weight1+1;weight2<=40-weight1;weight2++)
//注意：内循环起始值为外循环值加1
for(weight3=weight2+1;weight3<=40-weight1-weight2; weight3++)
if((weight4=40-weight1-weight2-weight3)>=weight3)
{
for(flag=1,x=1;x<41&&flag==1;x++)
//重物在天平左面，d的各种状态包括：-1：砝码在天平左面；
1：砝码在右面；0：不用该砝码
for(flag=0,d1=1;d1>-2;d1--) //三种状态都循环一遍
for(d2=1;d2>-2&&flag==0;d2--)
for(d3=1;d3>-2&&flag==0;d3--)
for(d4=1;d4>-2&&flag==0;d4--)
//找到组合，修改标志
if(x==weight1*d1+weight2*d2+ weight3*d3+weight4*d4)
flag=1;
if(flag==1)//flag为1代表组合找到了，为0代表组合没找到
{
System.out.printf("%d %d %d %dn",weight1, weight2,weight3,weight4);
w1=weight1; //找到组合，为下一步输出做准备
w2=weight2;
w3=weight3;
w4=weight4;
}

}
// System.out.printf("n%d %d %d %dn",w1,w2,w3,w4);
String left = "",right=""; //表达式初始化
//a1a2a3a4
for(int i=1;i<=40;i++) //循环40次，打印出每种情况
for(int a1=-1;a1<=1;a1++) //三种状态都循环一遍
for(int a2=-1;a2<=1;a2++)
for(int a3=-1;a3<=1;a3++)
for(int a4=-1;a4<=1;a4++)
{
if(i==a1*w4+a2*w3+a3*w2+a4*w1)
//如果相等，打印出结果
{
boolean f=true; //表达式右侧第一项标志
left=i+"";

switch (a1){ //根据状态，修改表达式
case -1://状态-1：左侧，修改左侧表达式
left=left+"+"+w4;
break;
case 1: //状态1：右侧，修改右侧表达式
if(f) //如果是右侧第一项，数值前 不用加“+”
right=right+w4;
else //如果不是右侧第一项，数值 前加“+”
right=right+"+"+w4;
f=false;
//右侧出现过数值，修改f标志位
break;

}
switch (a2){ //根据状态，修改表达式
case -1: //状态-1：左侧，修改左侧表达式
left=left+"+"+w3;
break;
case 1: //状态1：右侧，修改右侧表达式
// right=right+"+"+w3;
if(f) //如果是右侧第一项，数值前不用 加“+”
right=right+w3;
else
right=right+"+"+w3;
f=false;//右侧出现过数值，修改f标志位
break;

}
switch (a3){//根据状态，修改表达式
case -1: //状态-1：左侧，修改左侧表达式
left=left+"+"+w2;
break;
case 1: //状态1：右侧，修改右侧表达式
if(f) //如果是右侧第一项，数值前不用 加“+”
right=right+w2;
else
right=right+"+"+w2;
f=false;//右侧出现过数值，修改f标志位
break;

}
switch (a4){//根据状态，修改表达式
case -1: //状态-1：左侧，修改左侧表达式
left=left+"+"+w1;
break;
case 1: //状态1：右侧，修改右侧表达式
if(f) //如果是右侧第一项，数值前不用 加“+”
right=right+w1;
else
right=right+"+"+w1;
f=false;//右侧出现过数值，修改f标志位
break;

}
System.out.println(left+"="+right);
//输出表达式
}
left=""; //下次循环，清空
right="";
}
}
}

didimm

2.9  一维多项式计算
1．问题描述
对于一维多项式，就是包含一个变量的多项式，一个普遍的一维多项式示例如下：
P(x)=an–1xn–1+an–2xn–2+…+a1x+a0
一维多项式求值就是对于上述多项式，计算在指定的x处的函数值。例如：
P(x)=3x6+7x5–3x4+2x3+7x2–7x–15
计算该多项式在指定的x时，P(x)的函数值。
2．问题分析
这是一个数学表达式求值问题，假设我们要求x=2时表达式的值，那么我们可以采用如下的程序代码来实现：

double x=2.0;
double P;
P=3*x*x*x*x*x*x+7*x*x*x*x*x-3*x*x*x*x+2*x*x*x+7*x*x-7*x-15;
System.out.printf("P(%f)=%f",x,P);

但是，如果重新换一个多项式呢？那么我们就要重新改写代码，重列一个多项式表达式来进行计算。这样显然是比较麻烦的。有没有一个通用的办法来计算多项式的值呢？答案是肯定的，我们可以采用递推的方式。首先可以将上述多项式变形为如下的等价形式：
P(x)=(…((an–1x+an–2)x+an–3)x+…+a1)x+a0
通过这个表达式可以看出，只要从里往外一层一层地按照如下的方式递推，便可以计算得到整个一维多项式的值。
Rn–1=an–1
Rk=Rk+1x+ak,         k=n–2,…,1,0
通过一层一层地计算后，得到的R0便是多项式P(x)的值。
（1）确定程序框架
有了前面的分析，主要分两步：第一步，如何简单地把多项式表示出来；第二步，给定x的值，把多项式的值计算出来。程序的框架如下：

public class ch2_9
{
         public static void main(String[] args)
        {
                 //构造多项式
                 //计算多项式的值
         }
}

（2）构造多项式
通过前面的问题分析，我们可以知道表达式取决于x的指数及系数，这里我们假设x的指数是递增的，用一个数组存放x的系数，数组的第一项对应x的0次方，第二项对应x的1次方，……。程序的代码如下：

double a[]={-15.0,-7.0,7.0,2.0,-3.0,7.0,3.0};

（3）计算多项式的值
前面的问题分析已经找到了多项式的递推关系，我们可以通过循环的方式实现递推。程序的代码如下：

result=a[n-1];
for (i=n-2; i>=0; i--)                                //递推算法计算
{
         result=result*x+a[i];
}
return result;                                                //返回计算结果

（4）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：

import java.text.DecimalFormat;
public class ch2_9
{
         static double polynomial1D(double a[],int n,double x)
         {
                int i;
             double result;
             result=a[n-1];
             for (i=n-2; i>=0; i--)                //递推算法计算
                 {
                         result=result*x+a[i];
                 }
             return result;                                                                                //返回计算结果
         }
         public static void main(String[] args)
        {
                 int i;
             double a[]={-15.0,-7.0,7.0,2.0,-3.0,7.0,3.0};                //表达式的系数
             double[] x={-2.0,-0.5,1.0,2.0,3.7,4.0};                                //x值
                 double result;
                 
                DecimalFormat df = new DecimalFormat("0.0000000E000");        //数字格式
                 DecimalFormat df1 = new DecimalFormat("0.00");
               
                System.out.println("计算P(x)=3x6+7x5-3x4+2x3+7x2-7x-15的值");
                 for (i=0; i<6; i++)                                                                        //逐个计算结果
                 {
                         result=polynomial1D(a,7,x[i]);
                         System.out.print("x="+df1.format(x[i])+"时，p(x)="+df.format                        (result)+"\n");
                 }
             System.out.print("\n");
         }
}

didimm

2.11  非线性方程求解（牛顿迭代法）
1．问题描述
非线性方程指方程中包含一个变量的幂次不是1次。例如：y=4x2–3、y=sin(x)–3x+1等等。这种方程多数不存在求根公式，从而求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。牛顿迭代法是牛顿在17世纪提出的一种求解方程f(x)=0的方法。
用牛顿迭代法求解如下的非线性方程在x0=2.0附近的方程的解：

2．问题分析
牛顿迭代法的原理：设r是f(x)=0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y=f(x)的切线L，L的方程为y=f(x0)+f '(x0)(x–x0)，求出L与x轴交点的横坐标 x1=x0–f(x0)/f '(x0)，称x1为r的一次近似值，过点（x1,f(x1)）做曲线y=f(x)的切线，并求该切线与x轴的横坐标x2=x1–f(x1)/f '(x1)称x2为r的二次近似值，重复以上过程，得r的近似值序列{Xn}，其中Xn1=Xn–f(Xn)/f '(Xn)，称为r的n1次近似值。上式称为牛顿迭代公式。
（1）确定程序框架
上面详细分析了牛顿迭代法求解非线性方程的过程，由分析可知，除了非线性方程本身，还要用到非线性方程曲线的切线，所以还要准备好非线性方程的导数方程，然后通过牛顿迭代公式进行迭代，求出方程的近似解。程序的框架如下：

public class ch2_11
{
         public static void main(String[] args)
        {
                 //构造非线性方程
                 //构造非线性方程的导数方程
          //通过迭代公式求解
         }
}

（2）构造非线性方程
为简化代码，这里直接写出非线性方程。代码如下：

static double func(double x)                                                                 //待求解方程
{
     return x*x*x*x-3*x*x*x+1.5*x*x-4.0;
}

（3）构造导数方程
为简化代码，这里直接写出非线性方程。代码如下：

static double dfunc(double x)                                                                 //导数方程
{
     return 4*x*x*x-9*x*x+3*x;
}

（4）通过迭代公式求解
从前面的分析可知，其中Xn1=Xn–f(Xn)/f '(Xn)为牛顿迭代公式，通过它很容易写出代码，代码如下：

/**
*x代表初始值
*maxcyc代表迭代次数
*precision代表精确度
*得到结果，返回值为1，否则，返回值为0
*/
static int NewtonMethod(double[] x,int maxcyc,double precision)
{
     double x0,x1;
     int i;

    x0=x[0];                                                                                //参数传递迭代初始值
         i=0;
         while(i<maxcyc)                                                                //循环次数不超过设定最大数
     {
         if(dfunc(x0)==0.0)                                                //若通过初值，方法返回值为0
         {
             System.out.print("迭代过程中导数为0!\n");
             return 0;
         }
         x1=x0-func(x0)/dfunc(x0);                                //牛顿迭代计算
        if(Math.abs(x1-x0)<precision || Math.abs(func(x1))<precision)
                                                                                                //达到预设的结束条件
        {
             x[0]=x1;                                                                 //返回结果
            return 1;
         }
         else                                                                                 //未达到结束条件
                {
             x0=x1;                                                                 //准备下一次迭代
                }
                 i++;                                                                        //迭代次数累加
     }
     System.out.print("迭代次数超过预设值!仍没有达到精度！\n");
     return 0;
}        
（5）完整程序
现在我们就需要把刚才的程序进行组合，构成我们的完整程序：


public class ch2_11
{
         static double func(double x)                                 //待求解方程
        {
             return x*x*x*x-3*x*x*x+1.5*x*x-4.0;
         }
         static double dfunc(double x)                                 //导数方程
         {
             return 4*x*x*x-9*x*x+3*x;
         }
         static int NewtonMethod(double[] x,int maxcyc,double precision)
        {
             double x0,x1;
             int i;

            x0=x[0];                                                                        //参数传递迭代初始值i=0
                 while(i<maxcyc)                                                        //循环次数不超过设定最大数
             {
                 if(dfunc(x0)==0.0)                                        //若通过初值，方法返回值为0
                 {
                     System.out.print("迭代过程中导数为0!\n");
                     return 0;
                 }
                 x1=x0-func(x0)/dfunc(x0);                        //牛顿迭代计算
                if(Math.abs(x1-x0)<precision || Math.abs(func(x1))<precision)                                                                                                 //达到预设的结束条件
                {
                     x[0]=x1;                                                         //返回结果
                    return 1;
                 }
                 else                                                                         //未达到结束条件
                        {
                     x0=x1;                                                         //准备下一次迭代
                        }
                         i++;                                                                //迭代次数累加
             }
             System.out.print("迭代次数超过预设值!仍没有达到精度！\n");
             return 0;
         }
         public static void main(String[] args)
        {
                 double precision;
             int maxcyc,result;

                double[] x={2.0};                                                //初始值
                 maxcyc=1000;                                                        //迭代次数
                 precision=0.00001;                                                //精度
                 result=NewtonMethod(x,maxcyc,precision);
             if(result==1)                                                         //得到结果
                 {
                 System.out.printf("方程x*x*x*x-3*x*x*x+1.5*x*x-4.0=0\n在2.0附                近的根为:%f\n",x[0]);
                 }
             else                                                                                         //未得到结果
                 {
                 System.out.print("迭代失败!\n");
                 }
         }
}