トップページに戻る    次のC++のサンプルへ    前のC++のサンプルへ

Problem36 10進でも2進でも回文数になる数の総和

問題

585 = 10010010012 (2進) は10進でも2進でも回文数である.

100万未満で10進でも2進でも回文数になる数の総和を求めよ.

(注: 先頭に0を含めて回文にすることは許されない.)


ソース

#include <iostream>
#include <string>
#include <bitset>
#include <algorithm>
#include <Windows.h>
#include <stdio.h>

bool IsKaibun(std::string pTarget)
{
    std::string pTargetRev = pTarget;
    std::reverse(pTargetRev.begin(),pTargetRev.end());
    return pTarget == pTargetRev;
}

void main()
{
    int cnt = 0, SumVal = 0;

    //偶数は、2進数で1桁目が0なので、チェック対象外
    for(int I=1;I<=999999;I+=2){
        char DecStr[100];wsprintf(DecStr,"%d",I);
        if (IsKaibun(DecStr)==false) continue;

        std::bitset<20> InsBitSet((unsigned long)I);
        std::string BinStr = InsBitSet.to_string();

        //前ゼロの消去
        for(int J=0;J<=(int)BinStr.size()-1;J++){
            if (BinStr.at(J) == '1'){
                BinStr = BinStr.substr(J);
                break;
            }
        }
        if (IsKaibun(BinStr)==false) continue;
        printf("%3d番目は%7d。合計は%7d\n", ++cnt,I, SumVal+=I);
    }
}


実行結果

  1番目は      1。合計は      1
  2番目は      3。合計は      4
  3番目は      5。合計は      9
  4番目は      7。合計は     16
  5番目は      9。合計は     25
  6番目は     33。合計は     58
  7番目は     99。合計は    157
  8番目は    313。合計は    470
  9番目は    585。合計は   1055
 10番目は    717。合計は   1772
 11番目は   7447。合計は   9219
 12番目は   9009。合計は  18228
 13番目は  15351。合計は  33579
 14番目は  32223。合計は  65802
 15番目は  39993。合計は 105795
 16番目は  53235。合計は 159030
 17番目は  53835。合計は 212865
 18番目は  73737。合計は 286602
 19番目は 585585。合計は 872187


解説

stringクラスのsubstrメソッドでは、
Oracleのsubstr関数と同様に、第2引数を省略できます。

BitSetクラスのコンストラクタでは、ビット数を指定してます。
2の 8乗で    256
2の16乗で  65536
2の17乗で 131072
2の18乗で 262144
2の19乗で 524288
2の20乗で1048576
なので、バイト数として20を指定して、BitSetクラスのインスタンスを作成してます。

MSDN --- reverse
MSDN --- bitset Members
MSDN --- basic_string::substr