Yahoo奇摩知識+將於 2021 年 5 月 4 日 (美國東部時間) 終止服務。自 2021 年 4 月 20 日 (美國東部時間) 起,Yahoo奇摩知識+服務將會轉為唯讀模式。其他Yahoo奇摩產品與服務或您的Yahoo奇摩帳號都不會受影響。如需關於Yahoo奇摩知識+ 停止服務以及下載您個人資料的資訊,請參閱說明網頁。

? 發問時間: 電腦與網際網路程式設計 · 1 0 年前

急!!!求fortran高手解答

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

請問這個人若要從x走到y,最少需要走幾步?

舉例說明:若x=45,y=50,那麼每步走的長度可以是:1 2 1 1,所以最少需要走4步。

input

輸入的第一列有一個正整數代表以下有幾組測試資料。每組測試資料一列,含有2個整數x跟y(0<=x<=y<2的31次方)

output

每組測試資料輸出一列,最少需要走幾步才能從x走到y

例如input

3

45 48

45 49

45 50

output

3

3

4

1 個解答

評分
  • Jack
    Lv 5
    1 0 年前
    最佳解答

    根據走步規則,最有效率(每一步都能發揮最大功用)的是「金字塔型」的走步方式,像這樣: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

    (程式結束執行)

還有問題?馬上發問,尋求解答。