猴子吃桃问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
java版
《数据结构》
设计说明书
猴子吃桃问题
学生姓名 *小龙 学院 信电学院 班级 计算132 学号 13*******
一、课题任务
一群猴子摘了一堆桃子,他们每天都吃当前桃子的一半且再多吃一个,到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。
二、设计要求
1)采用数组数据结构实现上述求解
2)采用链数据结构实现上述求解
3)采用递归实现上述求解
三、程序的功能设计
能够采用数组、链表、递归的方法计算出桃子的总数。
四、函数编码及调试
1)数组形式
public class Array
{
public static void main(String[] args)
{
int day;
int peach[] = new int[11];
peach[0] = 0;
peach[1] = 1;
for (day = 2; day <= 10; day++)
peach[day] = (int) (3 * Math.pow(2, day - 1) - 2);
System.out.println("桃子一共有" + peach[10] + "个");
}
}
利用数组形式求解,设这个数组的下标表示天数,这个数组的值就是所代表那天的桃子数。利用这个地推公式a[i]=(a[i-1]+1)*2,就能求出每天桃子数的通项公式,即(3 * Math.pow(2, day - 1) - 2); 这样便能求出最开始的总共的桃子数
2)递归形式
public class Array
{
public static void main(String[] args)
{
System.out.println(f(1,10));
}
static int f(int n, int i)
{
if (i > 0)
{
n = f((n + 1) * 2, --i);
}
return n;
}
}
设计递归算法,利用x=2*x+2,定义一个函数f(),然后不断调用自身,求得
第一天的桃子数。
3)链表形式
public class Monkey { //主函数
public static void main(String[] args) {
List l = new List();
l.array();
l.link();
}
}
//构成链表的结点定义
public class Node {
public Node next;
public Object data;
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
public class List {
private Node Head = null;
private Node Tail = null;
private Node Pointer = null;
private int Length = 0;
//在当前结点前插入一个结点,并使其成为当前结点
public void insert(Object d) {
Node e = new Node(d, null);
if(Length == 0) {
Tail = e;
Head = e;
} else {
Node temp = cursor();
e.next = temp;
if(Pointer == null)
Head = e;
else
Pointer.next = e;
}
Length ++;
}
//将当前结点移出链表,下一个结点成为当前结点,如果移出的结
点是最后一个结点,则第一个结点成为当前结点
public Object remove() {
Object temp;
if(Length == 0)
return 0;
else if(Length == 1) {
temp = Head.data;
deleteAll();
}
else {
Node cur = cursor();
temp = cur.data;
if(cur == Head)
Head = cur.next;
else if(cur == Tail) {
Pointer.next = null;
Tail = Pointer;
reset();
}
else
Pointer.next = cur.next;
Length --;
}
return temp;
}
//返回当前结点的指针
private Node cursor() {
if(Head == null)
return null;
else if(Pointer == null)
return Head;
else
return Pointer.next;
}
//返回当前结点的值
public Object currentNode() {
Node temp = cursor();
return temp.data;
}
public void deleteAll() {
Head = null;
Tail = null;
Pointer = null;
Length = 0;
}
public void reset() {
Pointer = null;
}
//链表实现
public void link() {
int s = 0;
List a=new List ();
for(int i=1;i<=10;i++) {
if(a.Length == 9) {
s = 1;
while(a.Length != 0) {
s = s*2 + 2;
a.remove();
}
System.out.println("链表实现:");
System.out.println("桃子总数: " + s);
} else a.insert(new Integer(i));
}
}
//数组实现
public void array() {
int a[] = new int[10];
a[9] = 1;
for(int i=a.length-2; i>=0; i--) {
a[i] = 2 * a[i+1] +2;
}
System.out.println("数组实现:");
System.out.println("桃子总数: " + a[0]);
System.out.println("****************");
}
}
七、
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
这个问题是一个算法问题,要求用三种方式解决这个算法问题。 经过两个周的课程设计,体会到同样的问题用三种方法解决算法问题带来的不同和各自的优缺点,熟悉了三种方法的使用方法。
或许算法没有最好的,但是都在不断的探索更好的。但用java实现链表确实不太好,本来链表就比较难理解,用java实现链表确实违背了java面向对象的理念。但对于递归和数组来是实现这个算法太简单了。
算法是程序的灵魂,找打最优的算法是很重要的,所以很有必要好好学习接下来的算法。