华师一附中OI组

标题: 1000以内约数最多的数是哪个 [打印本页]
作者: admin    时间: 2020-2-11 11:28
标题: 1000以内约数最多的数是哪个
这是一个简单的统计题，一个很简单的思路是求出1-1000内每个数的约数个数，然后求出最大值
求约数的个数可以类似开关灯问题，只是不去设置灯的开关状态而是记录开关了多少次。

  1. #include <iostream>
  2. using namespace std;
  3. const int mn=1000;
  4. bool a[mn+5];
  5. int i,j;
  6. int main()
  7. {
  8.         for (i=1; i<=mn; i++) a[i]=0; ///预设每个数的约数为0
  9.         for (i=1; i<=mn; i++)
  10.                 {
  11.                         s=0; ///从0开始
  12.                         for (j=1; j<=mn; j++)
  13.                                 if (%j==0) s++; ///统计约数个数
  14.                         a[i]=s;///存起来
  15.                 }
  16.         maxs=-1;
  17.         for (i=1; i<=mn; i++) if (a[i]>maxs) maxs=s;///找最大值
  18.         cout<<s;
  19.         return 0;
  20. }
复制代码
作者: admin    时间: 2020-2-11 11:34
楼上那样做是在是太浪费了，我们完全没有必要记录下所有数的约数个数，其实可以一边求出约数的个数，就一边就和当前的最大值比较，大就保留，小或等就舍弃。
  1. #include <iostream>
  2. using namespace std;
  3. const int mn=1000;
  4. int i,j,s,maxs;
  5. int main()
  6. {
  7.         maxs=-1;///maxs赋初值
  8.         for (i=1; i<=1000; i++)
  9.                 {
  10.                         s=0; ///统计赋初值
  11.                         for (j=1; j<=1000; j++) if (i%j==0) s++; ///统计个数
  12.                         if (s>maxs)  maxs=s;///擂台比较
  13.                 }
  14.         cout<<maxs;
  15.         return 0;
  16. }
复制代码


作者: admin    时间: 2020-2-11 11:38
要是既想要求出最多约数的个数，又要求出这个数的话，就可以加一个标记变量，在记录maxs的时候同时记录maxi表示这个数，比较的时候只需要比较maxs和s但更新的时候不仅要更新maxs也需要更新maxi
  1. #include <iostream>
  2. using namespace std;
  3. const int mn=1000;
  4. int i,j,s,maxs,maxi;
  5. int main()
  6. {
  7.         maxs=-1;///maxs赋初值 maxi不用 想想为什么
  8.         for (i=1; i<=1000; i++)
  9.                 {
  10.                         s=0; ///统计赋初值
  11.                         for (j=1; j<=1000; j++) if (i%j==0) s++; ///统计个数
  12.                         if (s>maxs)  {maxs=s;maxi=i;}///更新两个
  13.                 }
  14.         cout<<maxs<<' '<<maxi;
  15.         return 0;
  16. }
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2