C语言 关于人过河的问题的源程序

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_STEP 20

//index: 0 - 狼，1－羊，2－菜，3－农夫，value：0－本岸，1－对岸

int a[MAX_STEP][4]

int b[MAX_STEP]

char *name[] =

{

"空手",

"带狼",

"带羊",

"带菜"

}

void search(int iStep)

{

int i

if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4)

{

for (i = 0i <iStepi++)

{

if (a[i][3] == 0)

{

printf("%s到对岸\n", name[b[i] + 1])

}

else

{

printf("%s回本岸\n", name[b[i] + 1])

}

}

printf("\n")

return

}

for (i = 0i <iStepi++)

{

if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0)

{

return

}

}

if (a[iStep][1] != a[iStep][3] &&(a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1]))

{

return

}

for (i = -1i <= 2i++)

{

b[iStep] = i

memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1]))

a[iStep + 1][3] = 1 - a[iStep + 1][3]

if (i == -1)

{

search(iStep + 1)

}

else if (a[iStep][i] == a[iStep][3])

{

a[iStep + 1][i] = a[iStep + 1][3]

search(iStep + 1)

}

}

}

int main()

{

search(0)

return 0

}

结果：

带羊到对岸

空手回本岸

带狼到对岸

带羊回本岸

带菜到对岸

空手回本岸

带羊到对岸

带羊到对岸

空手回本岸

带菜到对岸

带羊回本岸

带狼到对岸

空手回本岸

带羊到对岸

Press any key to continue

设n为石墩数,m为荷叶数 ,设F[n,m]表示当有n个石墩,m个荷叶时,能跳过去的最多青蛙数，我们现在可以增加一个石墩，此时就有n+1个石墩了,把第n+1个石墩看成右岸,这样就可以把F[n,m]个青蛙从左岸跳到第n+1个石墩上(借助原来河里的n个石墩,m个荷叶), 这时第n+1个石墩上就有F[n,m]个青蛙了，此时河里还有n个空石墩,m个空荷叶,还可以帮助F[n,m]个青蛙从左岸跳到真正的右岸,此时再把第n+1个石墩看成左岸, 借助河里的n个石墩,m个荷叶,顺利的跳到右岸青蛙的身上.至此一共可以跳过去 2*F[n,m]个青蛙.

由此可知： 关系式 F[n+1，m]=2*F[n，m]

推导: F[n，m]=2*F[n-1，m]

=4*F[n-2，m]

……

=(2^i)*F[n-i，m]

……

=(2^n)*F[0，m]

当n=0时,河里只有m个荷叶,每个叶上只能有一个青蛙,再加上从右岸可以直接跳到左岸的一只,所以共有m+1个青蛙,即F[0,m]=m+1所以

F[n，m]=(m+1）*2^n

这个是偶写的 你可以参考下 写的有点多 你自己优化下吧 之前还不知道农夫过河是啥意思 不过后来知道了 如果有问题的话可以马上说的 你的50分偶要定咯！！(可以直接运行)

import java.util.Iterator

import java.util.LinkedList

public class AcrossTheRiver {

// 定义三个String对象

public static final String rabbitName = "Rabbit"

public static final String wolfName = "Wolf"

public static final String cabbageName = "Cabbage"

// 判断两个货物之间关系是否友好 写的麻烦了一点= =..

public static boolean isFriendly(Goods goods1, Goods goods2) {

if (goods1 != null) {

if (goods1.getGoodsName().trim().equals(rabbitName)) {

if (goods2 == null) {

return true

} else {

return false

}

} else if (goods1.getGoodsName().trim().equals(wolfName)) {

if (goods2 == null || goods2.getGoodsName().trim().equals(cabbageName)) {

return true

} else {

return false

}

} else if (goods1.getGoodsName().trim().equals(cabbageName)) {

if (goods2 == null || goods2.getGoodsName().trim().equals(wolfName)) {

return true

} else {

return false

}

} else {

return false

}

} else {

return true

}

}

// 我就直接写在主方法里了

public static void main(String[] args) {

boolean isSuccess = false

LinkedList<Goods>beforeCrossing = new LinkedList<Goods>()

LinkedList<Goods>afterCrossing = new LinkedList<Goods>()

beforeCrossing.add(new Goods(rabbitName))

beforeCrossing.add(new Goods(cabbageName))

beforeCrossing.add(new Goods(wolfName))

while (!isSuccess) {

Goods goods1 = beforeCrossing.getFirst()

System.out.println(goods1.getGoodsName() + " 被取走了")

beforeCrossing.removeFirst()

if (beforeCrossing.isEmpty()) {

afterCrossing.addLast(goods1)

isSuccess = true

System.out.println("全部移动完毕！")

} else {

Iterator<Goods>it = beforeCrossing.iterator()

Goods[] beforeCro = new Goods[2]

for (int i = 0it.hasNext()i++) {

beforeCro[i] = it.next()

System.out.println(beforeCro[i].getGoodsName() + " 留了下来")

}

if (isFriendly(beforeCro[0], beforeCro[1])) {

if (afterCrossing.isEmpty()) {

afterCrossing.addLast(goods1)

System.out.println(goods1.getGoodsName() + " 被成功的放到了对岸")

} else {

Goods goods2 = afterCrossing.getFirst()

if (isFriendly(goods1, goods2)) {

afterCrossing.addLast(goods1)

System.out.println(goods1.getGoodsName() + " 被成功的放到了对岸")

} else {

beforeCrossing.addLast(goods2)

afterCrossing.removeFirst()

System.out.println(goods1.getGoodsName() + " 与 "

+ goods2.getGoodsName() + "并不和睦 于是把 " + goods2.getGoodsName()

+ "带了回来 并将 " + goods1.getGoodsName() + " 留了下来")

}

}

} else {

beforeCrossing.addLast(goods1)

System.out.println("很可惜 留下来的两个东西并不和睦 于是 " + goods1.getGoodsName()

+ " 又被放了回去")

}

}

}

}

}

// 货物类

class Goods {

// 货物名称

private String goodsName

// 默认构造方法

public Goods(String goodsName) {

this.goodsName = goodsName

}

// 获得货物名称

public String getGoodsName() {

return goodsName

}

}

---