谁能看出规律

honhon

B  缩小三角形
Time Limit:1000MS  Memory Limit:65535K
题型: 编程题   语言: 无限制
描述
刚接触算法的Gsh遇到了一道难题。给你一个边长为n的等边三角形，然后你可以对三角形进行如下操作：每次减少一条边的长度，但是要保证这三

条边还是能构成三角形。现在要求你把三角形缩小为边长为m的等边三角形，请问最少需要花多少步。Gsh想了很久都没想出来，你能帮帮他吗？


输入格式
输入两个数字n和m， (3&#8201;≤&#8201;m&#8201;<&#8201;n ≤&#8201;100&#8201;000)
注意题目是多case输入，输入格式为while(scanf("%d%d",&n,&m)>0){.....}（case数不超过100）


输出格式
输出一个整数，代表最少花费步数，每个case输出一行
输入样例
6 3
8 5
4 3
61 3
输出样例
4
3
3
9
Hint
一开始三角形的边长是（6，6，6），然后变成（6，6，3）->（6，4，3）->（3，4，3）->（3，3，3），一共花费了4步
61到3只用9步我愣是无法写出过程

honhon

急了，！研究一天了，还是没办法

honhon

自行AC了

人造人

我也写完了，你也解决了^_^
既然解决了，那就帮我看看我写的对不对

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. long reduce_triangle(long n, long m)
   
5. {
   
6.         long a = n;
   
7.         long b = n;
   
8.         long c = n;
   
9.         long ret = 0;
   
10. 
    
11.         if(!((3 <= m) && (m < n) && (n <= 100000)))
    
12.         {
    
13.                 return -1; //不符合条件
    
14.         }
    
15. 
    
16.         c = m;
    
17.         ret++;
    
18. 
    
19.         while((a != b) || (a != c) || (b != c))
    
20.         {
    
21.                 b = m;
    
22.                 while((b + c <= a) || (b + a <= c) || (a + c <= b))
    
23.                 {
    
24.                         b++;
    
25.                 }
    
26.                 ret++;
    
27. 
    
28.                 if((a == b) && (a == c) && (b == c))
    
29.                 {
    
30.                         break;
    
31.                 }
    
32. 
    
33.                 a = m;
    
34.                 while((b + c <= a) || (b + a <= c) || (a + c <= b))
    
35.                 {
    
36.                         a++;
    
37.                 }
    
38.                 ret++;
    
39.         }
    
40.        
    
41. 
    
42.         return ret;
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.         int n, m;
    
48. 
    
49.         printf("请输入n和m：");
    
50. 
    
51.         while(scanf("%d%d", &n, &m) > 0)
    
52.         {
    
53.                 printf("%ld\n", reduce_triangle(n, m));
    
54.                
    
55.         }
    
56. 
    
57.         return 0;
    
58. }
    

复制代码

honhon

人造人 发表于 2016-12-13 18:02
我也写完了，你也解决了^_^
既然解决了，那就帮我看看我写的对不对

错了哦，告诉当时我苦思冥想想不出来别人给我说的两个字 “逆推”，没错他只说了两个字就不鸟我，而我也顿悟了弄不懂在我问我哈，有上就回复

人造人

honhon 发表于 2016-12-15 16:37
错了哦，告诉当时我苦思冥想想不出来别人给我说的两个字 “逆推”，没错他只说了两个字就不鸟我，而我也 ...

哦

horn0603

我也写了这个程序，可就是不明白错在哪，可以求教一下吗？贴下代码或者给下思路

honhon

horn0603 发表于 2016-12-18 11:09
我也写了这个程序，可就是不明白错在哪，可以求教一下吗？贴下代码或者给下思路

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.     int n, m, i, j;
   
5.     while (scanf("%d %d", &n, &m) == 2){
   
6.         int t, a[3], count = 0;
   
7.         a[0] = a[1] = a[2] = m;
   
8.         while (a[0] != n || a[1] != n || a[2] != n){//printf("1\n");
   
9.             for (i = 0; i < 2; i++){
   
10.                 for (j = i; j < 2-i; j++){
    
11.                     if (a[j] > a[j+1]){
    
12.                         t = a[j];
    
13.                         a[j] = a[j+1];
    
14.                         a[j+1] = t;
    
15.                     }
    
16.                 }
    
17.             }
    
18.             if (a[1] + a[2] > n) a[0] = n;
    
19.               else a[0] = a[1] + a[2] - 1;
    
20.             count++;
    
21.             //printf("%d %d %d\n", a[0], a[1], a[2]);
    
22.         }
    
23.         printf("%d\n", count);
    
24.     }
    
25. }

复制代码

//没有注释，说明一下，我的思路的逆着来，变成放大三角形

horn0603

收到，我看看，理解理解。
多谢了

horn0603

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. #include<math.h>
   
5. void f(int array[])
   
6. {
   
7.     int temp;
   
8.     for (int i = 0; i < 2; i++)
   
9.     {
   
10.         for (int j = i; j < 2-i; j++)
    
11.         {
    
12.             if (array[j] > array[j+1])
    
13.             {
    
14.                 temp = array[j];
    
15.                 array[j] = array[j+1];
    
16.                 array[j+1] = temp;
    
17.             }
    
18.         }
    
19.     }
    
20. }
    
21. int main()
    
22. {
    
23.     int n, m;
    
24.     while (scanf("%d %d", &n, &m)>0)
    
25.     {
    
26.         int i,j,t, a[3], c = 0;
    
27.         a[0] = a[1] = a[2] = m;
    
28.         while (a[0] < n || a[1] < n || a[2] < n)
    
29.         {
    
30.             f(a);
    
31.             if (a[1] + a[2] <= n) a[0] = a[1] + a[2] - 1;
    
32.             else a[0] = n;
    
33.             c++;
    
34.         }
    
35.         printf("%d\n", c);
    
36.     }
    
37. }
    
38. //这样吗

复制代码

honhon

horn0603 发表于 2016-12-18 22:30
收到，我看看，理解理解。
多谢了

不用谢