在开班上学程序设计的时候会超出有关于求最大左券数与最小公倍数的主题材料,因为用辗转相除法很好的化解了这一难题。当然在大家刚开端学的时候有种不甚了了解的感到,那不是竟然的,毕竟是刚接触程序,同样也是第叁遍接触到有关算法的主题材料。在回忆明白的功底上那就不是三个标题了,和其他的文化同等,在我们回想了–掌握了–会运用了,那样就ok了。但是读书c或c++,笔者个人以为是和数学紧凑相连的,只怕以后参与了办事领头做一些的花色的时候不会太专心那些了。若是想学好编制程序,作者以为学好数据布局、组合数学、博艺论等等是必得的。因为自个儿个人对计算机编制程序也是发端涉猎,所以懂的亦不是不菲。说的也许又罗嗦有不在点上,敬请谅解。

主题素材陈述

• 给您2个分数,求他们的和,并供给和为最简格局。

• 那道题珍视考查的是递归算法,别的还附赠了三个GCD算法,你能做出来吗?

能够把代码提交至此处:http://acm.hdu.edu.cn/showproblem.php?pid=2503


A:

显赫物经济学家欧几Reade开采了生龙活虎种很粗略的主意–辗转相除法很简单地化解了这么些标题。在数学上用(a,b卡塔尔(قطر‎表示a,b的最大左券数。
定理:设a,b,c是随便八个不全为0的整数,且 a=bq+c
个中q是整数,则a,b与b,c有同等的公约数,即(a,b卡塔尔(قطر‎=(b,c卡塔尔。

解题解析

本次的标题就不再详明了,GCD就是求最大公约数的算法,其实就能够直接用高级中学学习的“辗转相除法”来求得;

用辗转相除法鲜明四个正整数 a 和 b(a≥b卡塔尔(قطر‎ 的最大公因数gcd(a,bState of Qatar:

当a mod b=0 时gcd(a,b)=b,否则

gcd(a,b) = gcd(b,a mod b)

是否相当的轻便,那就不赘述了,直接上代码。

1、编制程序将富有“金盏银台数”打字与印刷出来,并打字与印刷其总个数。“金盏银台数”是二个依次位立方之和至极该整数的贰位数。

#include  <iostream>

例程(C++)

(注:例程只是给出意气风发种解题方法,不是专门的职业程序,也不自然是最完美的解法)

#include<iostream>
using namespace std;
int Gcd(int x, int y);
int main()
{
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int son = a * d + b * c;
int mum = b * d;
int temp = Gcd(son, mum);
if (temp == 0) {
cout << temp << ” ” << 1 << endl;
}
else {
cout << son / temp << ” ” << mum / temp <<
endl;
}
}
system(“pause”);
return 0;
}
int Gcd(int x, int y)
{
if (x % y == 0) {
return y;
}
else {
return Gcd(y, x % y);
}
}

for (int i = 100; i < 1000; i++) {

using namespace std;
  
int main()
{
 int a, b, temp;
 int t;
 int sum ;

              int a, b, c;

 cout << ” Please input two number” << endl;
 cout << ” The frist one :”;
 cin >> a;
 cout << ” The second one :”;
 cin >> b;

              a = (i / 100) % 10;

 sum = a*b;

              b = (i / 10) % 10;

 if ( b > a)
 {
  temp = a;
  a = b;
  b = temp;
 }

              c = i % 10;

 while ( b )
 {
  t = a % b;
  a = b;
  b = t;
 }

              if (a*a*a +b*b*b +c*c*c == i) {

 cout << “最大协议数 :” << a << endl;
 cout << “最小公倍数 : ” << sum/a << endl;

                        Console.WriteLine (“{0}”,i);

 return 0;
}

             }

}

int sum = 0;

for (int i = 100; i < 1000; i++) {

               int a = (i / 100) % 10;

               int b = (i / 10) % 10;

               int c = i % 10;

               if (Math.Pow(a,3)+ Math.Pow(b,3)+ Math.Pow(c,3) == i) {

                         sum++;

                         Console.WriteLine (“{0}”,i);

             }

Console.WriteLine(sum);

}

2、自定义二个数组并求数组中的全体因素最大值、最小值、平均值及各因素之和。

float[] num = {1,2,3,4,5};

float max = 0;

float min = num[0];

float avg = 0;

float sum = 0;

for (int i = 0; i < num.Length; i++) {

           if (num[i]>=max) {                                
//max = max

                         max = num[i];

           }

           if (num[i]<=min) {                                
 //min = min >num[i]?num[i]:min;

                          min = num[i];

            }

           sum += num [i];

}

avg = sum / num.Length;

Console.WriteLine (“max={0},min={1},sum={2},ave={3}”,max,min,sum,avg);

3、已知abc+cba =
1333,个中a,b,c均为壹位数,编程求出满意条件的a,b,c全部结成。

for (int a = 1; a < 10; a++) {

            for (int b = 0; b < 10; b++) {

                         for (int c = 1; c < 10; c++) {

                                     if ((a*100 + b*10 +c)+(c*100
+b*10 +a) == 1333) {

                                     Console.WriteLine
(“a={0},b={1},c={2}”,a,b,c);

                             }

                  }

        }

}

4、打字与印刷100以内的具备质数. (只能被1和它本人整除的数是质数卡塔尔国

for (int i = 2; i < 100; i++) {

            bool tag = false;

            for (int j = 2; j <=i/2; j++) {

                       if (i%j == 0) {

                               tag = true;

                               break;

                       }

          }

         if (!tag) {

                 Console.WriteLine (“{0}:是质数”,i);

           }

}

5、输入七个数,求最大左券数和最小公倍数。(有二种办法:辗转相除法和经常方法)

常备方法

int a = int.Parse(Console.ReadLine());

int b = int.Parse(Console.ReadLine());

int min = a < b ? a : b;

int max_grs = 0;

          for (int i = 1; i <=min; i++) {

                      if (a%i == 0 && i == 0) {

                                max_grs = i;

                   }

}

Console.WriteLine (“最大左券数为:”+ max_grs);

Console.WriteLine (“最小公倍数为:”+ (a*b)/max_grs);

//辗转相除法

//120  56

Console.WriteLine(“请输入一个数:”卡塔尔国;

int num1 = int.Parse(Console.ReadLine());

Console.WriteLine(“请输入另多个数:”卡塔尔国;

int num2 = int.Parse(Console.ReadLine());

int a = num1; int b = num2;

int temp;

do {

            temp = a%b;                                                
   //120%56=8  56%8=0

            a = b;                                                      
         // a=56      a = 8

            b = temp;                                                  
      // b=8      b = 0(循环截至卡塔尔(قطر‎

} while (b != 0);

Console.WriteLine (“最大左券数为:{0}”,a卡塔尔国;

Console.WriteLine (“最小公倍数为:{0}”,(num1*num2)/a);

6、三球从100m高度自由落下,每一回曝腮龙门后反跳回原本中度的八分之四,再落下,再反弹。

求它在第14遍一败涂地时,共通过多少米?第拾次反弹多高

float sum, hight;

sum = 100.0f;

hight = 100.0f;

for (int i = 2; i <=10; i++) {

            hight /= 2.0f;

            sum += hight * 2;

  }

Console.WriteLine (“{0},{1}”,sum,hight/2);

B:

7、百钱百鸡难题:鸡翁生机勃勃值钱5;母鸡生机勃勃值钱3;鸡雏三值钱1,百钱买百鸡,问鸡翁鸡母鸡雏各几何?

//5x +3y +z/3 = 100;

//x + y + z = 100; =>z = 100-(x+y);

//15x +9y +100 -(x+y)=300; =>14x +8y = 200;

for (int x = 0; x <= 20; x++) {

           for (int y = 0; y < 34 ; y++) {

                       if (14*x +8*y == 200) {

                                 Console.WriteLine(“x={0},y ={1},z=
{2}”,x,y,100-(x+y));

                        }

             }

}

8、输入n,分别用*出口边长为n的真心菱形。举例:n = 3时,输出

                       i     空格j    *

      *              -2        2      1      (2n-1)-2*|i|

    * * *           -1        1      3

  * * * * *          0        0      5

     * * *            1        1      3

        *               2        2     1

int n = int.Parse (Console.ReadLine());

for (int i = -n+1; i <=n-1; i++) {

           for (int j = 0; j < Math.Abs(i); j++) {

                      Console.Write (” “);

             }

            for (int k = 0; k < (2*n-1)-2*Math.Abs(i); k++) {

                       Console.Write (“*”);

              }

Console.WriteLine ();

}

观念打字与印刷题8为空心棱形

int n = int.Parse (Console.ReadLine());            *

for (int i = -n+1; i <=n-1; i++) {

           for (int j = 0; j < Math.Abs(i); j++) {

                      Console.Write (” “);

            }

for (int k = 0; k < (2*n-1)-2*Math.Abs(i); k++) {

            if (k == 0 || k == (2*n-2)-2*Math.Abs(i)) {

                  Console.Write (“*”);

            } else {

Console.Write (” “);

            }

}

Console.WriteLine ();

}

            *

        *         *

      *                 *

         *          *

                *

//