Skip to content

Latest commit

 

History

History
587 lines (449 loc) · 20.2 KB

12.md

File metadata and controls

587 lines (449 loc) · 20.2 KB
Raw

十二、数学问题

问题

这是本章的解题部分。

1.可被 3 和 5 整除的自然数之和

编写一个程序，计算并打印所有可被 3 或 5 整除的自然数的和，直到用户输入的给定限制。

2.最大公约数

写一个程序，在给定两个正整数的情况下，计算并打印两者的最大公约数。

3.最小公倍数

写一个程序，在给定两个或更多正整数的情况下，计算并打印它们的最小公倍数。

4.小于给定数的最大素数

编写一个程序，计算并打印比用户提供的数字小的最大素数，该数字必须是正整数。

5.性感的黄金搭档

写一个程序，打印所有性感的黄金配对，直到用户输入的限制。

6.大量的数字

写一个程序，打印所有丰富的数字和他们的丰富，直到用户输入的数字。

7.友好的数字

编写一个程序，打印所有小于 1，000，000 的友好数字对的列表。

8.阿姆斯特朗数字

写一个程序，用三位数打印所有阿姆斯特朗的号码。

9.一个数的质因数

编写一个程序，打印用户输入的数字的质因数。

10.格雷编码

编写一个程序，显示所有 5 位数字的正常二进制表示、格雷码表示和解码格雷码值。

11.将数值转换为罗马数字

编写一个程序，给定用户输入的数字，打印它的罗马数字等价物。

12.最大排序序列

编写一个程序，确定并打印 100 万以内哪个数字产生最长的 Collatz 序列，以及它的长度是多少。

13.圆周率的计算

编写一个程序，计算精度为两位小数的π值。

14.验证 ISBNs

编写一个程序，验证用户以字符串形式输入的 10 位数值是否代表有效的 ISBN-10 数字。

解决方法

以下是上述问题解决部分的解决方案。

1.可被 3 和 5 整除的自然数之和

这个问题的解决方案是迭代从 3 (1 和 2 不能被 3 整除，所以测试它们没有意义)到用户输入的限制的所有数字。使用模运算检查数字除以 3 和 5 的其余部分是否为 0。然而，能够求和到更大极限的技巧是使用long long而不是int或long进行求和，这将导致在求和到 100，000 之前溢出:

int main()
{
   unsigned int limit = 0;
   std::cout << "Upper limit:";
   std::cin >> limit;

   unsigned long long sum = 0;
   for (unsigned int i = 3; i < limit; ++ i)
   {
     if (i % 3 == 0 || i % 5 == 0)
        sum += i;
   }

   std::cout << "sum=" << sum << std::endl;
}

2.最大公约数

两个或多个非零整数的最大公约数( gcd 简称)，也称为最大公约数( gcf )、最高公约数( hcf )、最大公约数( gcm )或最高公约数，是除以所有整数的最大正整数。有几种方法可以计算 gcd 一种有效的方法是欧几里德算法。对于两个整数，算法是:

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

这可以使用递归函数在 C++ 中非常简单地实现:

unsigned int gcd(unsigned int const a, unsigned int const b)
{
   return b == 0 ? a : gcd(b, a % b);
}

欧几里德算法的非递归实现应该如下所示:

unsigned int gcd(unsigned int a, unsigned int b)
{
   while (b != 0) {
      unsigned int r = a % b;
      a = b;
      b = r;
   }
   return a;
}

In C++ 17 there is a constexpr function called gcd() in the header <numeric> that computes the greatest common divisor of two numbers.

3.最小公倍数

两个或多个非零整数的最小公倍数 ( lcm )也称为最小公倍数，是可被所有整数整除的最小正整数。计算最小公倍数的一种可能方法是将问题简化为计算最大公约数。在这种情况下使用以下公式:

lcm(a, b) = abs(a, b) / gcd(a, b)

计算最小公倍数的函数可能如下所示:

int lcm(int const a, int const b)
{
   int h = gcd(a, b);
   return h ? (a * (b / h)) : 0;
}

要计算两个以上整数的 lcm ，可以使用标题<numeric>中的std::accumulate算法:

template<class InputIt>
int lcmr(InputIt first, InputIt last)
{
   return std::accumulate(first, last, 1, lcm);
}

In C++ 17 there is a constexpr function called lcm() in the header <numeric> that computes the least common multiple of two numbers.

4.小于给定数的最大素数

质数是只有两个除数的数，1 和数本身。要找到比给定数小的最大素数，你应该先写一个函数，确定一个数是否是素数，然后从给定数开始，向 1 方向调用这个函数，直到遇到第一个素数。有各种算法来确定一个数是否是质数。确定素性的常见实现如下:

bool is_prime(int const num) 
{
   if (num <= 3) { return num > 1; }
   else if (num % 2 == 0 || num % 3 == 0) 
   { 
      return false; 
   }
   else 
   {
      for (int i = 5; i * i <= num; i += 6) 
      {
         if (num % i == 0 || num % (i + 2) == 0) 
         {
            return false;
         }
      }
      return true;
   }
}

该功能可以如下使用:

int main()
{
   int limit = 0;
   std::cout << "Upper limit:";
   std::cin >> limit;

   for (int i = limit; i > 1; i--)
   {
      if (is_prime(i))
      {
         std::cout << "Largest prime:" << i << std::endl;
         return 0;
      }
   }
}

5.性感的黄金搭档

性感质数是彼此相差 6 的质数(例如 5 和 11，或 13 和 19)。还有相差两个的孪生素数和相差四个的表亲素数。

在前面的挑战中，我们实现了一个函数，该函数确定一个整数是否是素数。我们将在本练习中重用该函数。你要做的是检查如果一个数字n是质数，那么这个数字n+6也是质数，在这种情况下，把这一对打印到控制台上:

int main()
{
   int limit = 0;
   std::cout << "Upper limit:";
   std::cin >> limit;

   for (int n = 2; n <= limit; n++)
   {
      if (is_prime(n) && is_prime(n+6))
      {
         std::cout << n << "," << n+6 << std::endl;
      }
   }
}

你可以把它作为计算和显示性感的三胞胎、四胞胎和五胞胎的进一步练习。

6.大量的数字

一个大数，也称为一个过度数，是指它的适当除数之和大于数本身的数。一个数的适当除数是这个数的正质因数，而不是这个数本身。适当因子之和超过数本身的量叫做丰度。例如，数字 12 有适当的除数 1、2、3、4 和 6。他们的总和是 16，这使 12 成为一个充裕的数字。它的丰度是 4(即 16 - 12)。

为了确定适当除数的和，我们尝试从 2 到数的平方根的所有数(所有质因数都小于或等于这个值)。如果现在的数，我们称之为i，除以这个数，那么i和num/i都是除数。但是，如果它们相等(例如如果i = 3，和n = 9，那么i除 9，但是n/i = 3，我们只加i，因为适当的约数必须只加一次。否则，我们同时添加i和num/i并继续:

int sum_proper_divisors(int const number)
{
   int result = 1;
   for (int i = 2; i <= std::sqrt(number); i++)
   {
      if (number%i == 0)
      {
         result += (i == (number / i)) ? i : (i + number / i);
      }
   }
   return result;
}

打印大量的数字很简单，只需迭代到指定的极限，计算适当除数的总和，并将其与数字进行比较:

void print_abundant(int const limit)
{
   for (int number = 10; number <= limit; ++ number)
   {
      auto sum = sum_proper_divisors(number);
      if (sum > number)
      {
         std::cout << number << ", abundance=" 
                   << sum - number << std::endl;
      }
   }
}

int main()
{
   int limit = 0;
   std::cout << "Upper limit:";
   std::cin >> limit;

   print_abundant(limit);
}

7.友好的数字

如果一个数的适当除数之和等于另一个数的适当除数之和，则称两个数是友好的。一个数的适当除数是该数的正质因数，而不是该数本身。友好号码不应与友好号码混淆。例如，数字 220 有适当的除数 1、2、4、5、10、11、20、22、44、55 和 110，它们的和是 284。284 的适当除数是 1、2、4、71 和 142；他们的总数是 220。因此，数字 220 和 284 被认为是友好的。

这个问题的解决方案是迭代所有的数字，直到给定的极限。对于每个数，计算其适当除数的和。姑且称之为sum1。重复该过程，计算sum1的适当除数之和。如果结果等于原始数字，则数字和sum1是友好数字:

void print_amicables(int const limit)
{
   for (int number = 4; number < limit; ++ number)
   {
      auto sum1 = sum_proper_divisors(number);
      if (sum1 < limit)
      {
         auto sum2 = sum_proper_divisors(sum1);
         if (sum2 == number && number != sum1)
         {
            std::cout << number << "," << sum1 << std::endl;
         }
      }
   }
}

在上面的例子中，sum_proper_divisors()是在大数问题的解中看到的函数。

The above function prints pairs of numbers twice, such as 220,284 and 284,220. Modify this implementation to only print each pair a single time.

8.阿姆斯特朗数字

阿姆斯特朗数(以迈克尔·f·阿姆斯特朗的名字命名)，也称为自恋数、pluperfect 数字不变量或 pluperfect 数，是一个数，当它的位数增加到位数的幂时，它等于它自己的位数之和。举个例子，最小的阿姆斯特朗数是 153，等于。

要确定一个三位数的数字是否是自恋数字，你必须首先确定它的位数，以便对它们的幂求和。然而，这涉及除法和模运算，这是昂贵的。一种更快的计算方法是依赖于这样一个事实，即一个数是数字的总和乘以 10 的幂等于它们从零开始的位置。换句话说，对于 1000 以下的数字，我们有a*10^2 + b*10^2 + c。因为你只需要确定三位数的数字，这意味着a将从 1 开始。这将比其他方法更快，因为乘法的计算速度比除法和模运算更快。这种函数的实现如下所示:

void print_narcissistics()
{
   for (int a = 1; a <= 9; a++)
   {
      for (int b = 0; b <= 9; b++)
      {
         for (int c = 0; c <= 9; c++)
         {
            auto abc = a * 100 + b * 10 + c;
            auto arm = a * a * a + b * b * b + c * c * c;
            if (abc == arm)
            {
               std::cout << arm << std::endl;
            }
         }
      }
   }
}

你可以把它作为一个进一步的练习，写一个函数来决定自恋数字的上限，不管它们的位数是多少。这样的函数会比较慢，因为你首先必须确定数字的数字序列，将它们存储在一个容器中，然后将数字加到适当的幂(数字的数量)上。

9.一个数的质因数

正整数的质因数是将该整数整除的素数。例如，8 的质因数是 2×2×2，42 的质因数是 2×3×7。要确定主要因素，您应该使用以下算法:

  1. 而n可以被 2 整除，2 是质因数，必须加入列表，而n则成为n/2的结果。完成此步骤后，n为奇数。
  2. 从 3 迭代到n的平方根。而目前的数字，姑且称之为i，除n，i是质因数，必须加进榜单，而n则成为n/i的结果。当i不再除n时，将i增加 2(得到下一个奇数)。
  3. 当n是大于 2 的素数时，上述步骤不会导致n变为 1。因此，如果在第 2 步结束时n仍然大于 2，那么n就是一个主要因素。
std::vector<unsigned long long> prime_factors(unsigned long long n)
{
   std::vector<unsigned long long> factors;
   while (n % 2 == 0) {
      factors.push_back(2);
      n = n / 2;
   }
   for (unsigned long long i = 3; i <= std::sqrt(n); i += 2)
   {
      while (n%i == 0) {
         factors.push_back(i);
         n = n / i;
      }
   }

   if (n > 2) 
      factors.push_back(n);
   return factors;
}

int main()
{
   unsigned long long number = 0;
   std::cout << "number:";
   std::cin >> number;

   auto factors = prime_factors(number);
   std::copy(std::begin(factors), std::end(factors),
        std::ostream_iterator<unsigned long long>(std::cout, " "));
}

作为进一步的练习，确定数字 600，851，475，143 的最大质因数。

10.格雷编码

格雷码，也称为反射二进制码或简称反射二进制码，是二进制编码的一种形式，其中两个连续的数字仅相差一位。要执行二进制反射格雷码编码，我们需要使用以下公式:

if b[i-1] = 1 then g[i] = not b[i]
else g[i] = b[i]

这相当于以下内容:

g = b xor (b logically right shifted 1 time)

对于解码二进制反射格雷码，应使用以下公式:

b[0] = g[0]
b[i] = g[i] xor b[i-1]

对于 32 位无符号整数，可以用 C++ 编写如下:

unsigned int gray_encode(unsigned int const num)
{
   return num ^ (num >> 1);
}

unsigned int gray_decode(unsigned int gray)
{
   for (unsigned int bit = 1U << 31; bit > 1; bit >>= 1)
   {
      if (gray & bit) gray ^= bit >> 1;
   }
   return gray;
}

要打印所有 5 位整数、它们的二进制表示、编码的格雷码表示和解码值，我们可以使用以下代码:

std::string to_binary(unsigned int value, int const digits)
{
   return std::bitset<32>(value).to_string().substr(32-digits, digits);
}

int main()
{
   std::cout << "Number\tBinary\tGray\tDecoded\n";
   std::cout << "------\t------\t----\t-------\n";

   for (unsigned int n = 0; n < 32; ++ n)
   {
      auto encg = gray_encode(n);
      auto decg = gray_decode(encg);

      std::cout 
         << n << "\t" << to_binary(n, 5) << "\t" 
         << to_binary(encg, 5) << "\t" << decg << "\n";
   }
}

11.将数值转换为罗马数字

今天已知的罗马数字使用七个符号:I = 1，V = 5，X = 10，L = 50，C = 100，D = 500，M = 1000。系统在组成数字符号时使用加法和减法。从 1 到 10 的符号是 I、II、III、IV、V、VI、VII、VIII、IX 和 x。罗马人没有零的符号，他们用写 nulla 来表示它。在这个系统中，最大的符号在左边，最不重要的符号在右边。例如，1994 的罗马数字是 MCMXCIV。如果你不熟悉罗马数字的规则，你应该在网上多看看。

要确定数字的罗马数字，请使用以下算法:

  1. 从最高(M)到最低(I)检查每个罗马基本符号
  2. 如果当前值大于符号的值，则将符号连接到罗马数字，并从当前值中减去它的值
  3. 重复，直到当前值为零

例如，考虑 42:小于 42 的第一个罗马基本符号是 XL，即 40。我们将其连接到数字上，得到 XL，然后从当前数字中减去，得到 2。第一个小于 2 的罗马基符号是 I，也就是 1。我们把它加到数字上，得到 XLI，然后从数字中减去 1，得到 1。我们在数字上再加一个 I，变成 XLII，再从数字中减去 1，达到 0，因此停止:

std::string to_roman(unsigned int value)
{
   std::vector<std::pair<unsigned int, char const*>> roman {
      { 1000, "M" },{ 900, "CM" }, { 500, "D" },{ 400, "CD" }, 
      { 100, "C" },{ 90, "XC" }, { 50, "L" },{ 40, "XL" },
      { 10, "X" },{ 9, "IX" }, { 5, "V" },{ 4, "IV" }, { 1, "I" }};

   std::string result;
   for (auto const & kvp : roman) {
      while (value >= kvp.first) {
         result += kvp.second;
         value -= kvp.first;
      }
   }
   return result;
}

该功能可以如下使用:

int main()
{
   for(int i = 1; i <= 100; ++ i) 
   {
      std::cout << i << "\t" << to_roman(i) << std::endl; 
   }

   int number = 0;
   std::cout << "number:";
   std::cin >> number;
   std::cout << to_roman(number) << std::endl;
}

12.最大排序序列

柯拉茨猜想，也称为乌兰猜想、卡库塔尼问题、思韦特猜想、哈塞算法或锡拉丘兹问题，是一个未经证实的猜想，它指出如下所述定义的序列总是达到 1。级数定义如下:从任意正整数n开始，从上一项得到每个新项:如果上一项为偶数，则下一项为上一项的一半，否则为上一项的 3 倍加 1。

你要解决的问题是为所有 100 万以内的正整数生成 Collatz 序列，确定其中最长的一个，并打印它的长度和产生它的起始数。虽然我们可以应用蛮力为每个数字生成序列，并计算项数直到达到 1，但更快的解决方案是保存已经生成的所有序列的长度。当从值n开始的序列的当前项变得小于n时，那么它是一个已经确定了序列的数字，所以我们可以简单地获取它的缓存长度，并将其添加到当前长度中，以确定从n开始的序列的长度。然而，这种方法对可以计算的 Collatz 序列引入了限制，因为在某个时刻，缓存将超过系统可以分配的内存量:

std::pair<unsigned long long, long> longest_collatz(
   unsigned long long const limit)
{
   long length = 0;
   unsigned long long number = 0;
   std::vector<int> cache(limit + 1, 0);

   for (unsigned long long i = 2; i <= limit; i++) 
   {
      auto n = i;
      long steps = 0;
      while (n != 1 && n >= i) 
      {
         if ((n % 2) == 0) n = n / 2;
         else n = n * 3 + 1;
         steps++ ;
      }
      cache[i] = steps + cache[n];

      if (cache[i] > length) 
      {
         length = cache[i];
         number = i;
      }
   }

   return std::make_pair(number, length);
}

13.圆周率的计算

近似确定π值的一个合适的解决方案是使用蒙特卡罗模拟。这是一种使用随机输入样本来探索复杂过程或系统行为的方法。该方法被用于各种各样的应用和领域，包括物理、工程、计算、金融、商业和其他领域。

要做到这一点，我们将依靠以下想法:直径为d的圆的面积为PI * d^2 / 4。边长等于d的正方形面积是d^2。如果我们把两者分开，我们会得到PI/4。如果我们把圆放在正方形里面，生成在正方形里面均匀分布的随机数，那么圆里面的个数应该和圆的面积成正比，正方形里面的个数应该和正方形的面积成正比。这意味着将方块和圆圈中的点击总数相除应该会给出PI/4。生成的点越多，结果应该越准确。

为了生成伪随机数，我们将使用默森扭转器和均匀的统计分布:

template <typename E = std::mt19937, 
          typename D = std::uniform_real_distribution<>>
double compute_pi(E& engine, D& dist, int const samples = 1000000)
{
   auto hit = 0;
   for (auto i = 0; i < samples; i++)
   {
      auto x = dist(engine);
      auto y = dist(engine);
      if (y <= std::sqrt(1 - std::pow(x, 2))) hit += 1;
   }
   return 4.0 * hit / samples;
}

int main()
{
   std::random_device rd;
   auto seed_data = std::array<int, std::mt19937::state_size> {};
   std::generate(std::begin(seed_data), std::end(seed_data), 
                 std::ref(rd));
   std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
   auto eng = std::mt19937{ seq };
   auto dist = std::uniform_real_distribution<>{ 0, 1 };

   for (auto j = 0; j < 10; j++)
      std::cout << compute_pi(eng, dist) << std::endl;
}

14.验证 ISBNs

国际标准书号 ( 国际标准书号)是图书的唯一数字标识符。目前，使用 13 位格式。但是，对于这个问题，您需要验证使用 10 位数字的前一种格式。10 位中的最后一位是校验和。选择该数字是为了使所有十个数字的总和(每个数字乘以其(整数)权重，从 10 到 1 递减)是 11 的倍数。

validate_isbn_10函数，如下所示，将一个 ISBN 作为一个字符串，如果字符串的长度为 10，所有十个元素都是数字，并且所有数字的总和乘以它们的权重(或位置)是 11 的倍数，则返回true:

bool validate_isbn_10(std::string_view isbn)
{
   auto valid = false;
   if (isbn.size() == 10 &&
       std::count_if(std::begin(isbn), std::end(isbn), isdigit) == 10)
   {
      auto w = 10;
      auto sum = std::accumulate(
         std::begin(isbn), std::end(isbn), 0,
         [&w](int const total, char const c) {
            return total + w-- * (c - '0'); });

     valid = !(sum % 11);
   }
   return valid;
}

You can take it as a further exercise to improve this function to also correctly validate ISBN-10 numbers that include hyphens, such as 3-16-148410-0. Also, you can write a function that validates ISBN-13 numbers.