C++
 Computer >> コンピューター >  >> プログラミング >> C++

C++で数字3と4のみを使用して作成できる、最大N桁の数の個数を求める

問題概要

整数 N が与えられたとき、数字「3」と「4」のみを使って作成できる数の個数を求めます。たとえば、最大2桁までとすると、作成できる数は 3、4、33、34、43、44 の6個になります。

アプローチ

この問題は、規則性に注目することで簡単に解くことができます。1桁の数は「3」と「4」の2個、2桁の数は「33」「34」「43」「44」の4個あります。同様に、m桁の数は 2m 個存在します。

したがって、最大N桁までに作成できる数の総数は、等比数列の和の公式より次のように表せます。

21 + 22 + … + 2N = 2(N+1) − 2

実装例（C++）

#include<iostream>
#include<cmath>
using namespace std;
long long countNumbers(int n) {
    return (long long)(pow(2, n + 1)) - 2;
}
int main() {
    int n = 3;
    cout << "Number of values: " << countNumbers(n);
}

出力

Number of values: 14

計算量

この解法は pow 関数を1回呼び出すだけで済むため、時間計算量・空間計算量ともに O(1) となり、非常に効率的です。ループや再帰を使わずに即座に答えを求められる点が大きなメリットといえます。

  1. C++で各桁がすべて奇数となるN番目の数を効率的に求める方法

    C++には数学的な問題を解決するための豊富な関数群が用意されています。その中でも、各桁がすべて奇数で構成される数列の中からN番目の数を求めるというのは、興味深い数学的課題の一つです。この記事では、奇数とは何か、そして「各桁がすべて奇数である数」とはどのような数なのかを理解した上で、N番目の数を求めるための完全なアプローチを解説します。 各桁がすべて奇数で構成されるN番目の数を求める まず基本のおさらいです。奇数とは2で割ると余りが1になる数のことで、小さい順に並べると 1, 3, 5, 7, 9, 11, 13, 15, 17, 19... となります。 ここで求めたいのは「各桁の数字がすべて

  2. C++でN番目の偶数長回文数を求める方法をわかりやすく解説

    C++を使ったことがある人なら、「回文（パリンドローム）」という言葉を耳にしたことがあるでしょう。この記事では、「N番目の偶数長回文数」について、具体例を交えながらすべて解説します。 回文とは、逆から読んでも元と同じになる数字や単語のことです。数字だけでなく、文字を反転してもつづりが変わらない単語も回文と呼ばれます。例えば以下の通りです。 数字 = {1, 121, 131, 656, 1221, 1551} 単語 = {saas, malayalam, level, mom} 一見複雑に見えますが、実際にプログラムで実装すると非常にシンプルです。それでは、回文について詳しく見ていきましょう。