第1章の記録

第1章は数学の問題でした。数学そのものを関心の対象としている訳ではなく、数学を題材にしたウォーミングアップといったところです。アームストロング数などといった知らないものは主にWikipediaを参考にしつつ、コーディング自体は自力でやりました。

「プログラミングの問題の多くには、どうしようもな遅い単純解と、比較的が良く知られているさらに難しい解とがある」(Optimized C++ 5章より)そうです。ここに挙げるコードは、前者の遅い単純解といったところでしょう。

問題1 3または5で割り切れる正の整数の総和

第1問目。一見すごく簡単そうですが、一つ落し穴がありました。0から指定された数までループしならが、条件を満す数の場合、合計を保持するための変数に加算していきます。この合計を保持する変数を適当にunsigned intとかしてしまうと、割とすぐに上限に達してしまいます。ですので、unsigned long longとかにする必要があります。

// 問題1 3または5で割り切れる正の整数の総和

#include <boost/lexical_cast.hpp>
#include <boost/lexical_cast/bad_lexical_cast.hpp>
#include <iostream>
using namespace std;

auto main(int argc, char **argv) -> int {
  if (argc != 2) {
    cerr << "bad arguments\n";
    return 1;
  }

  auto n = 0ULL;
  try {
    n = boost::lexical_cast<unsigned long long>(argv[1]);
  } catch (boost::bad_lexical_cast &e) {
    cerr << e.what() << '\n';
    return 1;
  }

  auto sum = 0ULL;
  for (auto i = 0; i <= n; ++i) {
    if (i % 3 == 0 || i % 5 == 0) {
      sum += i;
    }
  }

  cout << sum << '\n';
}

模範解答との比較

問題には「与えられた数の上限までの‥」とあって、上限の数をユーザーが指定できるようにすることが求められています。そのため、上限の数をコマンドライン引数で取ることにして、整数値に変換するためにboost::lexical_castを使いました。しかし、上限を受け取る方法はこの問題の主題ではないようで、単にcinから読み取るだけで十分だったようです。

auto n = 0;
cin >> n;

エラーチェックも関心の対象ではないので省略してよさそうでした。

問題2 最大公約数

ユークリッドの互除法と呼ばれる、有名なアルゴリズムの問題です。数aとbがあって、aをbで割ったときの余り(剰余)をとして、最大公約数を求める関数をgcdとした場合、gcd(a, b) = gcd(b, r)となることから、gcdを再帰的に適用していくことでaとbの最大公約数が求まるというものです。停止条件は、r=0となったときで、このときの除数bがaとbの最大公約数です。何言ってるか分かりにくいかもしれません。ちゃんとした証明を見ておいた方がいいです。

// 問題2 最大公約数

#include <iostream>
using namespace std;

auto main() -> int {
  auto a = 0;
  auto b = 0;

  cin >> a >> b;
  if (!cin) {
    return 1;
  }

  if (a == 0 || b == 0) {
    return 1;
  }

  do {
    auto r = a % b;
    a = b;
    b = r;
  } while (b != 0);

  cout << a << '\n';
}

模範解答との比較

模範解答として2つのパターンが載ってました。再帰版とループ版です。再帰版の方が数学での考え方をそのまま記述されているようで理解しやすいです。上の自分の書いたのはループ版の失敗作のようなものです。ユークリッドの互除法の原理を理解せず、ググって手続だけトレースしたら変なコードになってしまったというところです。

問題3 最小公倍数

// 問題3 最小公倍数

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <numeric>
using namespace std;

auto lcm2(unsigned long long a, unsigned long long b) -> unsigned long long {
  auto ma = 1;
  auto mb = 1;
  auto ta = a;
  auto tb = b;
  while (ta != tb) {
    if (ta < tb) {
      ++ma;
      ta = a * ma;
    } else {
      ++mb;
      tb = b * mb;
    }
  }
  return ta;
}

auto lcm(vector<unsigned long long> const &nums) -> unsigned long long {
  if (nums.empty()) {
    return 0;
  }

  if (nums.size() == 1) {
    return nums[0];
  }

  auto result = nums[0];
  using nums_size_type = vector<unsigned long long>::size_type;
  for (auto i = nums_size_type{1}; i < nums.size(); ++i) {
    result = lcm(result, nums[i]);
  }

  return result;
}

int main() {
  auto v = vector<unsigned long long>();
  copy(istream_iterator<unsigned>{cin}, istream_iterator<unsigned>{}, back_inserter(v));

  auto res = lcm(v);
  cout << res << endl;

  auto res2 = 0;
  if (!v.empty()) {
    res2 = accumulate(next(v.begin()), v.end(), v.front(), lcm2);
  }
  cout << res2 << endl;
}

問題4 与えられた正の整数より小さい最大の素数

// 問題4 与えられた正の整数より小さい最大の整数

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

auto sieve_eratosthenes(unsigned n) -> unsigned {
  if (n < 2) {
    return 0;
  }

  auto sieve = vector<bool>(n, true);
  sieve[0] = false;
  sieve[1] = false;

  auto sqrt_n = sqrt(n);
  for (auto i = 2u; i < sqrt_n; ++i) {
    if (sieve[i]) {
      auto j = i * i;
      while (j < n) {
        sieve[j] = false;
        j += i;
      }
    }
  }

  using sieve_size_type = vector<bool>::size_type;
  for (auto ri = sieve_size_type{sieve.size() - 1}; ri >= 0; --ri) {
    if (sieve[ri]) return ri;
  }

  return 0;
}

int main() {
  auto n = 0u;
  cin >> n;

  auto prime = sieve_eratosthenes(n);

  cout << n << endl;
}

模範解答との比較

テキストの解答では、6k±1という法則を利用したアルゴリズムを用いています。ここはもっと初歩的なエラトステネスの篩で判定しています。そのため効率は良くないです。

問題5 セクシー素数

// 問題5 セクシー素数

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

auto sieve_eratosthenes(unsigned n) -> vector<bool> {
  auto sieve = vector<bool>(n, true);
  sieve[0] = false;
  sieve[1] = false;

  auto sqrt_n = sqrt(n);
  for (auto i = 2u; i < sqrt_n; ++i) {
    if (sieve[i]) {
      auto j = i * i;
      while (j < n) {
        sieve[j] = false;
        j += i;
      }
    }
  }

  return sieve;
}

int main() {
  auto n = 0u;
  cin >> n;

  auto sieve = sieve_eratosthenes(n);

  using sieve_size_type = vector<bool>::size_type;
  for (auto i = sieve_size_type{2}; i + 6 < sieve.size(); ++i) {
    if (sieve[i] && sieve[i + 6]) {
      cout << i << " and " << i + 6 << " are sexy\n";
    }
  }
}

問題6 過剰数

// 問題6 過剰数

// https://ja.wikipedia.org/wiki/%E9%81%8E%E5%89%B0%E6%95%B0
// 過剰数とは、その約数の総和が元の数の2倍より大きい自然数のことである。
// この過剰数の定義は「その数自身を除く約数の総和が元の数より大きくなるような自然数」と同値である。

#include <iostream>
#include <cmath>
using namespace std;

auto sum_divisors(unsigned n) -> unsigned {
  auto s = 0u;
  auto sqrt_n = static_cast<unsigned>(sqrt(n));

  for (auto i = 1u; i <= n; ++i) {
    if (n % i == 0) {
      s += (i == (n / i)) ? i : (i + n / i);
    }
  }
  return s;
}

auto is_abundant(unsigned n) -> bool {
  auto s = sum_divisors(n);
  return s > n;
}

int main() {
  auto n = 0u;
  cin >> n;

  for (auto i = 0u; i < n; ++i) {
    if (is_abundant(i)) {
      auto abundant = sum_divisors(i) - i;
      cout << i << " is abundant " << abundant << ".\n";
    }
  }
}

問題7 友愛数

// 問題7 友愛数

// https://ja.wikipedia.org/wiki/%E5%8F%8B%E6%84%9B%E6%95%B0
// 友愛数とは、異なる2つの自然数の組で、自分自身を除いた約数の和が、互いに他方と等しくなるような数をいう。

#include <cmath>
#include <iostream>
using namespace std;

auto sum_divisors(unsigned n) -> unsigned {
  if (n < 2) {
    return 0;
  }

  auto s = 1u;
  auto sqrt_n = static_cast<unsigned>(sqrt(n));
  for (auto i = 2u; i <= sqrt_n; ++i) {
    if (n % i == 0) {
      s += (i == (n / i)) ? i : (i + n / i);
    }
  }
  return s;
}

int main() {
  auto const n = 1'000'000u;
  for (auto i = 0u; i < n; ++i) {
    auto a = sum_divisors(i);
    auto b = sum_divisors(a);
    if (i == b) {
      cout << i << " and " << a << " are amicable.\n";
    }
  }
}

問題8 アームストロング数

// 問題8 アームストロング数

#include <iostream>
using namespace std;

auto cubed(int x) -> int { return x * x * x; }

auto sum_cubed(int a, int b, int c) -> int {
  return cubed(a) + cubed(b) + cubed(c);
}

auto main() -> int {
  for (auto x = 100; x <= 999; ++x) {
    auto d1 = x % 10;
    auto d2 = x % 100 / 10;
    auto d3 = x / 100;

    if (sum_cubed(d1, d2, d3) == x) {
      cout << x << '\n';
    }
  }
}

問題9 素因数分解

// 問題9 素因数分解

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

auto main() -> int {
  auto x = 0;
  cin >> x;
  if (x < 1) {
    cout << "Gimme a positive number\n";
    return 1;
  }

  auto xsqrt = int(sqrt(x));
  auto factors = vector<int>();
  for (auto f = 2; f <= xsqrt; ++f) {
    while (x % f == 0) {
      factors.push_back(f);
      x /= f;
    }
  }

  for (auto f : factors) {
    cout << f << '\n';
  }
}

問題10 グレイコード

// 問題10 グレイコード
//
// https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%AC%E3%82%A4%E3%82%B3%E3%83%BC%E3%83%89

#include <iostream>
#include <bitset>
using namespace std;

template <size_t size>
auto encode(bitset<size> b) -> bitset<size> {
  static_assert(size > 0);
  return b ^ ((b >> 1).set(size - 1, false));
}

template <size_t size>
auto decode(bitset<size> g) -> bitset<size> {
  static_assert(size > 2);
  for (size_t i = 1; i < size; ++i) {
    auto const j = size - 1 - i;
    g[j] = g[j] ^ g[j + 1];
  }
  return g;
}

auto main() -> int {
  for (auto u = 0U; u <= 0b11111U; ++u) {
    auto b = bitset<5>{u};
    auto g = encode(b);
    auto decoded = decode(g);
    cout << u << '\t' << b << '\t' << g << '\t' << decoded << '\n';
  }

  auto b = bitset<4>{"1111"};
  cout << decode(b) << endl;
}

問題11 ローマ数字に変換

// 問題11 ローマ数字に変換

#include <cassert>
#include <iostream>
#include <list>
#include <map>
#include <string>
using namespace std;

auto to_roman(unsigned n) -> string {
  static auto symbol = map<unsigned, char>{
      {1, 'I'},   {5, 'V'},   {10, 'X'},   {50, 'L'},
      {100, 'C'}, {500, 'D'}, {1000, 'M'},
  };

  if (n >= 4000) {
    return "N/A";
  }

  auto s = list<char>();
  auto m = 1;

  while (n > 0) {
    auto r = n % 10;
    auto one = symbol[m];
    auto five = symbol[m * 5];
    auto ten = symbol[m * 10];

    if (r < 4) {
      for (auto i = 0; i < r; ++i) {
        s.push_front(one);
      }
    } else if (r == 4) {
      s.push_front(five);
      s.push_front(one);
    } else if (r < 9) {
      for (auto i = 0; i < r - 5; ++i) {
        s.push_front(one);
      }
      s.push_front(five);
    } else {
      assert(r == 9);
      s.push_front(ten);
      s.push_front(one);
    }

    n /= 10;
    m *= 10;
  }

  return string(s.begin(), s.end());
}

auto main() -> int {
  for (int i = 3001; i < 3100; ++i) {
    cout << i << ": " << to_roman(i) << endl;
  }

  cout << to_roman(3999) << endl;
}

問題12 最長コラッツ数列

// 問題12 最長コラッツ数列

#include <iostream>
#include <cassert>
using namespace std;

auto collatz(unsigned n) -> unsigned {
  assert(n > 0);
  auto length = 1U;
  while (n != 1) {
    if (n % 2 == 0) {
      n /= 2;
    } else {
      n = 3 * n + 1;
    }
    ++length;
  }
  return length;
}

auto main() -> int {
  auto maxlen = 0U;
  auto maxnum = 0U;
  for (auto i = 1U; i <= 1'000'000; ++i) {
    auto l = collatz(i);
    if (l > maxlen) {
      maxlen = l;
      maxnum = i;
    }
  }

  cout << maxnum << ": " << maxlen << endl;
}

問題13 πの計算

// 問題13 πの計算

#include <iomanip>
#include <iostream>
using namespace std;

auto main() -> int {
  auto pi = 0.0L;
  for (auto i = 1; i <= 1'000'000; ++i) {
    if (i % 2 != 0) {
      pi += 1.0L / (i * 2 - 1);
    } else {
      pi -= 1.0L / (i * 2 - 1);
    }
  }

  pi *= 4.0;

  cout << fixed << setprecision(10) << pi << endl;
}

問題14 ISBNの検証

// 問題14 ISBNの検証
//
// https://ja.wikipedia.org/wiki/ISBN

#include <algorithm>
#include <cctype>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;

auto is_valid_isbn_format(string_view sv) -> bool {
  auto s = string();
  transform(sv.begin(), sv.end(), back_inserter(s),
            [](unsigned char c) { return toupper(c); });

  auto begpos = 0;
  if (auto b = s.find_first_of("ISBN"); b == 0) {
    begpos = 4;
  } else if (b != string::npos) {
    return false;
  }

  auto hyphen_count = 0;
  auto digit_count = 0;
  for (string::size_type i = begpos; i < s.length(); ++i) {
    if (s[i] == '-') {
      if (i == begpos || i == s.length() - 1) {
        return false;
      }
      if (s[i - 1] == '-') {
        return false;
      }
      ++hyphen_count;
    } else if (isdigit(s[i])) {
      ++digit_count;
    } else {
      return false;
    }
  }

  if (digit_count != 10 || hyphen_count > 3) {
    return false;
  }

  return true;
}

auto is_valid_isbn_check_digit(string_view sv) -> bool {
  auto s = string();
  copy_if(sv.begin(), sv.end(), back_inserter(s),
          [](unsigned char c) { return isdigit(c) || c == 'X'; });

  if (s.length() != 10) {
    return false;
  }

  auto check_digit = string(1, s.back());
  s.pop_back();

  auto weight = 10;
  auto sum = 0;
  for (auto c : s) {
    auto d = c - '0';
    sum += d * weight;
    --weight;
  }
  auto r = sum % 11;
  auto check_result = to_string(11 - r);

  if (check_result == "10") {
    check_result = "X";
  }

  return check_result == check_digit;
}

auto main() -> int {
  auto s = string{};
  cin >> s;
  cout << is_valid_isbn_format(s) << endl;

  // cout << is_valid_isbn_format("4044281084") << ' '
  //      << is_valid_isbn_check_digit("4044281084") << endl;

  // auto isbn1 = "ISBN4-10-109205-X"s;
  // cout << is_valid_isbn_check_digit(isbn1) << endl;
}