Pairs of Numbers 辗转相除

# 42. Pairs of Numbers

https://blog.csdn.net/qq_43521140/article/details/107853492

- 出题人：OJ
- 标签：["DFS and Similar"]
- 难度：简单
- 总分数：100

## 题目描述
<p>Let's assume that we have a pair of numbers (a,b). We can get a new pair (a+b,b) or (a,a+b) from the given pair in a single step.</p><p>Let the initial pair of numbers be (1,1). Your task is to find number k, that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals n.</p>

## 解答要求
时间限制：1000ms, 内存限制：100MB

## 输入
<p>The input contains the only integer n (1 ≤ n ≤ 10<sup>6</sup>).<b>Process to the end of file</b>.</p>

## 输出
<p>Print the only integer k.</p>

## 样例
### 输入样例 1:
```
5
1
```
### 输出样例 1:
```
3
0

```
## 提示

```
package main
import "fmt"
var tmp int
var leastep int
func main() {
   var n int
   for {
      _, err := fmt.Scanf("%d", &n)
      if err != nil {
         return
      } else if n == 1 {
         fmt.Printf("0\n")
         continue
      } else if n == 2 {
         fmt.Printf("1\n")
         continue
      }
      leastep = n - 1
      for i:= 1;i<n;i++{
         tmp = 0
         dfs(n,i)
         leastep = minint(tmp,leastep)
      }
      //leastep = n + 1
      //for i := n/2 + 1; i < n && i/(n-i) <= leastep; i++ {
      // leastep = minint(leastep, leaststeps(i, n-i, 1))
      //}
      fmt.Printf("%d\n", leastep)
   }
}
func minint(a, b int) int {
   if a >= b {
      return b
   } else {
      return a
   }
}
func dfs(a,b int){
   if b == 1{
      tmp += a-1
      return
   }
   tmp += a/b
   dfs(b,a%b)
}

func leaststeps(a, b, steps int) int {
   if b == 1 {
      return a - 1 + steps
   } else if a%b == 0 {
      return leastep + 1
   } else if steps >= leastep {
      return leastep + 1
   } else {
      return leaststeps(b, a%b, steps+a/b)
   }
}

```
巴特西

Pairs of Numbers 辗转相除

最新文章

热门文章
