honhon 发表于 2016-12-13 08:00:53

谁能看出规律

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

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


输入格式
输入两个数字n和m， (3 ≤ m < n ≤ 100 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步我愣是无法写出过程{:10_312:}

honhon 发表于 2016-12-13 12:14:23

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

honhon 发表于 2016-12-13 17:38:23

自行AC了{:10_256:}

人造人 发表于 2016-12-13 18:02:26

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

#include <stdio.h>
#include <stdlib.h>

long reduce_triangle(long n, long m)
{
        long a = n;
        long b = n;
        long c = n;
        long ret = 0;

        if(!((3 <= m) && (m < n) && (n <= 100000)))
        {
                return -1; //不符合条件
        }

        c = m;
        ret++;

        while((a != b) || (a != c) || (b != c))
        {
                b = m;
                while((b + c <= a) || (b + a <= c) || (a + c <= b))
                {
                        b++;
                }
                ret++;

                if((a == b) && (a == c) && (b == c))
                {
                        break;
                }

                a = m;
                while((b + c <= a) || (b + a <= c) || (a + c <= b))
                {
                        a++;
                }
                ret++;
        }
       

        return ret;
}

int main()
{
        int n, m;

        printf("请输入n和m：");

        while(scanf("%d%d", &n, &m) > 0)
        {
                printf("%ld\n", reduce_triangle(n, m));
               
        }

        return 0;
}

honhon 发表于 2016-12-15 16:37:39

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

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

人造人 发表于 2016-12-15 16:44:56

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

哦

horn0603 发表于 2016-12-18 11:09:35

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

honhon 发表于 2016-12-18 16:48:41

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

#include <stdio.h>
int main()
{
    int n, m, i, j;
    while (scanf("%d %d", &n, &m) == 2){
      int t, a, count = 0;
      a = a = a = m;
      while (a != n || a != n || a != n){//printf("1\n");
            for (i = 0; i < 2; i++){
                for (j = i; j < 2-i; j++){
                  if (a > a){
                        t = a;
                        a = a;
                        a = t;
                  }
                }
            }
            if (a + a > n) a = n;
            else a = a + a - 1;
            count++;
            //printf("%d %d %d\n", a, a, a);
      }
      printf("%d\n", count);
    }
}//没有注释，{:10_279:}说明一下，我的思路的逆着来，变成放大三角形

horn0603 发表于 2016-12-18 22:30:22

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

horn0603 发表于 2016-12-18 22:51:53

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
void f(int array[])
{
    int temp;
    for (int i = 0; i < 2; i++)
    {
      for (int j = i; j < 2-i; j++)
      {
            if (array > array)
            {
                temp = array;
                array = array;
                array = temp;
            }
      }
    }
}
int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m)>0)
    {
      int i,j,t, a, c = 0;
      a = a = a = m;
      while (a < n || a < n || a < n)
      {
            f(a);
            if (a + a <= n) a = a + a - 1;
            else a = n;
            c++;
      }
      printf("%d\n", c);
    }
}
//这样吗

honhon 发表于 2016-12-19 15:56:46

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

不用谢
页: [1]
查看完整版本: 谁能看出规律