关于java源代码青蛙过河的信息

电脑编程问题

dp压缩

这是解题报告

第二题 过河-River

[问题分析]

此题初看是一个典型的搜索题。从河的一侧到河的另一侧，要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。

如果搜索石子，方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划，以石子分阶段的一维动规，时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律，而且会有后效性。

这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索，然后再加上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为O(m2)。[批注：号称一词已成为湖南OI本世纪流行词汇 ]

[题目实现]

先以时间为对象进行搜索。时间复杂度为O(L)。从桥的一侧到另一侧，中间最多只有100个石子。假设桥长为最大值(109)，石头数也为最大值(100)。这样中间一定会有很多“空长条” (两个石子中的空地)，处理时把这些跳过，就只会有M次运算。关键是找出每一个可以跳过的“空长条”。

我们可以先把青蛙可以跳出的所有可能求出，然后就可以求出可以忽略的“空长条”。

[特殊算法]

a[i]:前i个坐标中石子最小个数,初始为第i个坐标的石子个数

b[i]:第i个石子坐标

动规

a[0]=0;

对n=t

a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}

对s=nt

a[n]=max{a[n]+a[n-s],a[n]+a[n-s-1],...,a[n]+a[0]}

但由于n较大直接动规会超时。所以要将n压缩

查看坐标，可以发现，如果b[i]-b[i-1]t，显然对于b[i-1]+tnb[i]，a[n]总是等于a[b[i-1]]..a[b[i-1]+t]中的数，因此可对其进行压缩。

注意，在计算过程中，由于其中有一些坐标是永远走不到的，因此需要用一个布尔型的数组c[n]进行判断。方法是，对于c[n],如果0ns,则c[n]为false，如果ns,c[n-t],c[n-t+1],...,c[n-s]都为false,则c[n]也为false。

这个我试了,是对的

type arr=array[0..100000] of longint;

var a,f,stone,stone2:arr;

l,s,x,t,m,n,o,p,i,j,k,min:cardinal;

procedure deal;

var i:longint;

begin

stone[0]:=0;

stone[m+1]:=l;

for i:=1 to m+1 do

if stone[i]-stone[i-1]=100 then stone2[i]:=stone2[i-1]+100

else stone2[i]:=stone2[i-1]+stone[i]-stone[i-1];

end;

begin

readln(l);

readln(s,t,m);

for i:=1 to m do

read(stone[i]);

if s=t then begin

for i:=1 to m do

if stone[i] mod s=0 then inc(o);

writeln(o);

end

else begin

for i:=1 to m-1 do

for j:=1 to m-i do

if stone[j]stone[j+1] then begin

stone[0]:=stone[j];

stone[j]:=stone[j+1];

stone[j+1]:=stone[0];

end;

Deal;

l:=stone2[m+1];

for i:=1 to m do

a[stone2[i]]:=1;

f[0]:=0;

for i:=1 to l+t do begin

f[i]:=maxlongint-1;

for j:=t downto s do

if ij then break

else

if (f[i-j]+a[i])f[i] then f[i]:=f[i-j]+a[i];

end;

min:=maxlongint;

for i:=l to l+t do begin

if f[i]min then min:=f[i];

end;

writeln(min);

end;

end.

说了就是状态压缩dp

求：C语言课设游戏青蛙过河源代码！

设n为石墩数,m为荷叶数 ,设F[n,m]表示当有n个石墩,m个荷叶时,能跳过去的最多青蛙数，java源代码青蛙过河我们现在可以增加一个石墩，此时就有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]个青蛙.

由此可知java源代码青蛙过河： 关系式 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

java青蛙过河背景怎么弄

背景图片需要放在JFramejava源代码青蛙过河的JLayeredPane层中,而且需要把覆盖在其上面java源代码青蛙过河的JPanel设成透明,才能作为背景被显示出来.java源代码青蛙过河我给你个例子,你看看吧.

import java.awt.BorderLayout;

import javax.swing.ImageIcon;

import javax.swing.JButton;

import javax.swing.JFrame;

import javax.swing.JLabel;

import javax.swing.JLayeredPane;

import javax.swing.JPanel;

public class BackGroundPicture extends JFrame{

 JButton jb=new JButton("打印");

 ImageIcon image=new ImageIcon("Penguins.jpg");//这里背景图片文件换成你java源代码青蛙过河的背景图片文件

 JLabel jl=new JLabel(image);//添加背景图片

 JPanel jp = new JPanel();

 public BackGroundPicture(){

  super("图片打印窗口");

  jp.add(jb);

  jp.setOpaque(false);

  JLayeredPane jlp=this.getLayeredPane();

  jlp.setLayout(new BorderLayout());

  jlp.add(jl);

    this.add(jp);

  this.setSize(800, 600);

  this.setLocationRelativeTo(null);

  this.setDefaultCloseOperation(this.EXIT_ON_CLOSE);

  this.setResizable(true);

  this.setVisible(true);

 }

 public static void main(String[] args) {

  new BackGroundPicture();

 }

}

请问这道java题怎么做？

Java源代码：

public class Test {

public static void main(String[] args) {

Point p1 = new Point(4, 5);

System.out.printf("点p坐标为（%f,%f）\n", p1.getX(), p1.getY());

p1.setX(3);

p1.setY(4);

System.out.printf("重置后点p坐标为（%f,%f）\n", p1.getX(), p1.getY());

System.out.printf("点（%f, %f）到原点的距离的平方为%f\n", p1.getX(), p1.getY(),

p1.distance());

Point p2 = new Point(1, 2);

System.out.printf("点（%f,%f）到点（%f,%f）的距离的平方为%f\n", p1.getX(),

p1.getY(), p2.getX(), p2.getY(), p1.distance(p2));

}

}

class Point {

protected double x;

protected double y;

public Point(){

}

public Point(double x, double y) {

this.x = x;

this.y = y;

}

public void setX(double x) {

this.x = x;

}

public double getX() {

return this.x;

}

public void setY(double y) {

this.y = y;

}

public double getY() {

return this.y;

}

public double distance() {

return Math.pow(x, 2) + Math.pow(y, 2);

}

public double distance(Point p) {

return Math.pow(this.x - p.x, 2) + Math.pow(this.y - p.y, 2);

}

}

运行测试：

java源代码青蛙过河的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于、java源代码青蛙过河的信息别忘了在本站进行查找喔。