急!!!求fortran高手解答

Question

一個人沿著一數線前進。他每次走的長度（整數）必須是正的，而且比上一步走的長度多１，一樣，或少１。另外請注意：第一步跟最後一步的長度必須是１。

請問這個人若要從ｘ走到ｙ，最少需要走幾步？

舉例說明：若ｘ＝４５，ｙ＝５０，那麼每步走的長度可以是：１　２　１　１，所以最少需要走４步。

input
輸入的第一列有一個正整數代表以下有幾組測試資料。每組測試資料一列，含有２個整數ｘ跟ｙ（０＜＝ｘ＜＝ｙ＜２的３１次方）
 
output
每組測試資料輸出一列，最少需要走幾步才能從ｘ走到ｙ

例如input
3
45   48
45   49
45   50

output

3
3
4

Jack · Accepted Answer

根據走步規則，最有效率（每一步都能發揮最大功用）的是「金字塔型」的走步方式，像這樣：n=1
1（步數=1，距離=1）n=2
1 2 1（步數=3，距離=4）n=3
1 2 3 2 1（步數=5，距離=9）n=4
1 2 3 4 3 2 1（步數=7，距離=16）n=5
1 2 3 4 5 4 3 2 1（步數=9，距離=25）n=6
1 2 3 4 5 6 5 4 3 2 1（步數=11，距離=36）
：
：以上可歸納出一個規則：步數 = 2n-1，距離 = n^2。
步數很明顯。距離也不難證明：距離 = (1 加到 n) 再加上 (1 加到 n-1) = n(n+1)/2 + (n-1)n/2 = n^2。當距離恰巧是平方數，例如 36 時，可直接套用 n=6 的情形；當距離不是平方數，則視它與次一級平方數（m^2=25，m = n-1）的差距，可分成兩種狀況：(a) 當差距為 1 到 5（即 1 到 m），可套用 n=5 的情形，並且把差距那個數字重複一次。例如：距離 = 29，走法為 1 2 3 4 5 4 4 3 2 1（即 4 重複一次），步數 = 10（即 2m）。(b) 當差距為 6 到 10（即 m+1 到 2m），可套用 n=5 的情形，並且把 5（即 m）重複一次，差距減 5 那個數字也重複一次。例如：距離 = 33，走法為 1 2 3 4 5 5 4 3 3 2 1（即 5 和 3 重複一次），步數 = 11（即 2m+1）。程式如下： program main
 implicit none
 integer*4 na(1000), nb(1000), n, nd, iq, ir, i
1  write (*, "(/'Input:')")
 read *, n
 if (n <= 0) stop
 do i = 1, n
 read *, na(i), nb(i)
 end do
 write (*, "(/'Output:')")
 do i = 1, n
 nd = nb(i) - na(i)
 if (nd <= 0) then
 write (*, *) 'Illegal input'
 cycle
 end if
 iq = int(dsqrt(dfloat(nd)))
 ir = nd - iq*iq
 if (ir == 0) then
 write (*,*) iq*2-1
 else if (ir <= iq) then
 write (*,*) iq*2
 else
 write (*,*) iq*2+1
 end if
 end do
 go to 1
 end執行結果：Input:
3
45 48
45 49
45 50Output:
 3
 3
 4Input:
6
0 25
0 27
0 29
0 31
0 33
0 35Output:
 9
 10
 10
 11
 11
 11Input:
0
（程式結束執行）

急!!!求fortran高手解答

1 個解答