锐客网

  1. 首页 > 睿知 > it技术 > >

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

IT技术石墩

电脑编程问题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 ijthen 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;
【关于java源代码青蛙过河的信息】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源代码青蛙过河的信息别忘了在本站进行查找喔 。

    推荐阅读


    上一篇：苹果ios10.0apn，苹果15手机价格和图片颜色

    下一篇：ftp服务器的创建，怎么在ftp服务器上创建账号