小黑屋的一道数学题

digimondm

于是是at+b么。。
(a, b) -> (at, b)，遍历每个可能的(a, b)即可，每个t，对于潜艇必在(at, b)，只要遍历到开始(a, b)，放置(at, b)即可


好好玩

Renee

总之~~潜艇的速度~~可以有无限多种可能~~但是它的值本身不可能无限大~~

Conflux

globals
ingeger T = 0
integer P
integer 初始位置
integer 速度
endglobals
function 打中了没 takes integer i returns boolean
set P = 初始位置 + 速度 * T
return i==P
endfunction
function 丢炸弹 takes nothing returns nothing
local integer i = 0
local integer p
local integer v
local integer b = false
loop
set p=0
set v=i
loop
set b= 打中了没(p+T*v)
exitwhen b
set T= T+1
set b= 打中了没(p-T*v)
exitwhen b
set T= T+1
set b= 打中了没(-p+T*v)
exitwhen b
set T= T+1
set b= 打中了没(-p-T*v)
exitwhen b
set T= T+1
set p= p+1
exitwhen p==i+1
endloop
exitwhen b
set p=i
set v=0
loop
set b= 打中了没(p+T*v)
exitwhen b
set T= T+1
set b= 打中了没(p-T*v)
exitwhen b
set T= T+1
set b= 打中了没(-p+T*v)
exitwhen b
set T= T+1
set b= 打中了没(-p-T*v)
exitwhen b
set T= T+1
set v= v+1
exitwhen v==i+1
endloop
exitwhen b
set i = i+1
endloop
call BJDebugMsg("打中了...")
call BJDebugMsg("T="+I2S(T))
call BJDebugMsg("P="+I2S(P))
endfunction
function main takes nothing returns nothing
set 初始位置 = RandomInt(-1000,1000)
set 速度 = RandomInt(-1000,1000)
call 丢炸弹()
endfunction

cccty1l

假设初始地点是P，速度是V。

我在第0秒在0点放雷，那么（P，V）组合中所有的P=0都能排除掉。

接下来可试试（P，V）为（1，0），第1秒在1点放雷，满足P+V=1可以排除了。

然后第2秒试试（1，-1），在-1点放，满足P+2V=-1的排除。

3，（1，1），在4点，排除P+3V=4

4，（-1，-1），在-5点，排除P+4V=-5

5，（-1，0），被2排除，（-1，1），在4点，排除P+5V=4

6，（-2，2），被3排除，（-1，2），被1排除，（1，2），在13点，排除P+6V=13

7，（2，2），在16点，排除P+7V=16

。。。

我没算错吧....

cccty1l

找的话感觉怎样都行，但是怎么证明它是有限步呢？

唉，俺是对这个一窍不通

====================
没法合并了呀！

Renee

这个帖子是解篇：
http://bbs.islga.org/read-htm-tid-37682.html

joker1987

偶然看到这个帖子哈,很感兴趣,不知道算不算挖坟啊?
自己做了一下,有不足之处望海涵,jass不会,用的java
public class main
{
    static long starttime=System.currentTimeMillis();
    static int speed=3,startlocation=255,direction=0;
   public static void main(String args[])
   {
      
      
       System.out.println("program start");
       function();
      
   }
   private static void bomb(int speed2,int startlocation2,int direct)
   {
      
       int location;
       int time=(int)((System.currentTimeMillis()-starttime)*0.001);
       int bomblocation;
       int road=(int)((System.currentTimeMillis()-starttime)*0.001);
       if(direct==1)
       {
           bomblocation=startlocation2+time*speed2;
       }
       else
       {
           bomblocation=startlocation2-time*speed2;
       }
       if(direction==1)
       {
           location=startlocation+speed*time;
       }
       else
       {
           location=startlocation-speed*time;
       }
       try
       {
       Thread.currentThread().sleep(1000);
       }
       catch(Exception e)
       {
           
       }
       System.out.println("当前假定速度为"+speed2+"起始位置为"+startlocation2+"方向为"+direct);
       System.out.println("炸弹扔在"+bomblocation+"处"+"潜艇在"+location+"处"+"当前运行了"+time);
       if(bomblocation==location)
       {
           System.out.println("done");
            
           System.exit(0);
       }
   }

   private static void function()
   {
       int speed=1;
       int startlocation=0;
       int temp=0;
       while(true)
       {
           bomb(speed,startlocation,1);
           bomb(speed,-startlocation,1);
           bomb(speed,startlocation,0);
           bomb(speed,-startlocation,0);
          if(temp==0)
          {
              speed++;
              temp=1;
          }
          else
          {
              startlocation++;
              temp=0;
          }
       }
   }
}
------------------------------------------
关于此算法有穷性的简单证明:
假设潜水艇速度为v,起始位置为n,位置为一布尔数
设function为基本操作单位,则算法执行v*n*2个基本操作.
又因v,n都wei确定整数,则v*n*2必然为一整数;
故此算法必然可在有限基本操作单位内完成.


数学很烂,证明更烂,不知道有什么地方出错了还请大家多多指教.

joker1987

上面的有点问题,补充一下
基本操作单位应该为bomb()
算法执行基本操作量应为v*n*4
上面的算法取速度为3，开始位置255，负向运动,可以正常运行,但是由于这个算法特殊性.....所以就不多试了
证明不是很严谨,呵呵