论坛 › 欧拉计划（Project Euler） › 题目36：求出100万以下所有十进制和二进制表示都是回文的数字之和

欧拉计划 发表于 2015-4-23 23:56:34

题目36：求出100万以下所有十进制和二进制表示都是回文的数字之和

本帖最后由 永恒的蓝色梦想 于 2020-6-3 19:05 编辑

Double-base palindromes

The decimal number, (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)
题目：

十进制数字 (二进制),可以看出在十进制和二进制下都是回文（从左向右读和从右向左读都一样）。

求 100 万以下所有在十进制和二进制下都是回文的数字之和。

（注意在两种进制下的数字都不包括最前面的 0）

迷雾少年 发表于 2016-8-30 11:38:38

0:(2)(10)0
1:(2)1(10)1
3:(2)11(10)3
5:(2)101(10)5
7:(2)111(10)7
9:(2)1001(10)9
33:(2)100001(10)33
99:(2)1100011(10)99
313:(2)100111001(10)313
585:(2)1001001001(10)585
717:(2)1011001101(10)717
7447:(2)1110100010111(10)7447
9009:(2)10001100110001(10)9009
15351:(2)11101111110111(10)15351
32223:(2)111110111011111(10)32223
39993:(2)1001110000111001(10)39993
53235:(2)1100111111110011(10)53235
53835:(2)1101001001001011(10)53835
73737:(2)10010000000001001(10)73737
585585:(2)10001110111101110001(10)585585

#include <iostream>
#include <string>
using namespace std;
string calc(int n)
{
        string result;
        /* 转为二进制 不断取余*/
        while (n)
        {
                result+=(char)((n%2)+'0');
                n/=2;
        }
        reverse(result.begin(),result.end());
        return result;

}
/* 是否为回文数字 */
bool is(string n)
{
        char *buf = (char*)n.data();
       
        int len = strlen(buf);
        char *p1,*p2;
        p1 = buf;
        p2 = buf + len - 1;
        while (p1<p2 && *p1 == *p2 )
        {
                p1++;
                p2--;
        }
   return p1>=p2;
}
int main(void)
{

        for (int i=0;i<1000000;i++)
        {
                char buf;
                itoa(i,buf,10);
                string str(buf);
                if(is(calc(i)) && is(str))
                {
                        std::cout<<i<<":"<<"(2)"<<calc(i)<<"(10)"<<i<<endl;
                }
        }
        return 0;
}

愤怒的大头菇 发表于 2016-9-3 10:26:15

def Rec(number):
      temp = list(number)
      temp.reverse()
      tmp = list(number)
      if temp == tmp:
            return True
      return False
      


list1=[]
for i in range(1,1000000):
      n = str(i)
      if Rec(n):
            temp = bin(i)
            if Rec(str(temp)):
                  list1.append(i)

print(sum(list1))
结果：872187

芒果加黄桃 发表于 2017-1-14 09:22:53

# encoding:utf-8
# 寻找100万以下的十进制和二进制都是回文数的数之和
from time import time

def euler036(N=1000000):
    print(sum( and str(bin(i)) == str(bin(i))[::-1]]))
if __name__ == '__main__':
    start = time()
    euler036(1000000)
    print('cost %.6f sec' % (time() - start))

872187
cost 0.666491 sec

渡风 发表于 2017-6-14 21:57:17

此代码使用matlab编程
Problem36所用时间为： 0.21198秒
Problem36的答案为： 872187
%% Problem36.m
% 最后编辑时间：17-06-14 22:10
% 找出100w以下的数使得，其二进制数和十进制数都为回文数，求其和
% Problem36所用时间为： 0.21198秒
% Problem36的答案为： 872187
function Output = Problem36()
tic
Output = 0;
%个位数
for aa = 1:9
    if fliplr(num2str(dec2bin(aa))) == num2str(dec2bin(aa))
      Output = Output + aa;
    end
end
%十位数
for aa = 1:9
    if fliplr(num2str(dec2bin(aa*10 + aa))) == num2str(dec2bin(aa*10 + aa))
      Output = Output + aa*10 + aa;
    end
end

%百位数
for aa = 1:9
    for bb = 0:9
       if fliplr(num2str(dec2bin(aa*100 + bb*10 + aa))) == num2str(dec2bin(aa*100 + bb*10 + aa))
          Output = Output + aa*100 + bb*10 + aa;
       end
    end
end

%千位数
for aa = 1:9
    for bb = 0:9
       if fliplr(num2str(dec2bin(aa*1000 + bb*100 + bb*10 + aa))) == num2str(dec2bin(aa*1000 + bb*100 + bb*10 + aa))
          Output = Output + aa*1000 + bb*100 + bb*10 + aa;
       end
    end
end

%万位数
for aa = 1:9
    for bb = 0:9
      for cc = 0:9
            if fliplr(num2str(dec2bin(aa*10000 + bb*1000 + cc*100 + bb*10 + aa))) == num2str(dec2bin(aa*10000 + bb*1000 + cc*100 + bb*10 + aa))
                Output = Output + aa*10000 + bb*1000 + cc*100 + bb*10 + aa;
            end
      end
    end
end

%十万位
for aa = 1:9
    for bb = 0:9
      for cc = 0:9
            if fliplr(num2str(dec2bin(aa*100000 + bb*10000 + cc*1000 + cc*100 + bb*10 + aa))) == num2str(dec2bin(aa*100000 + bb*10000 + cc*1000 + cc*100 + bb*10 + aa))
                Output = Output + aa*100000 + bb*10000 + cc*1000 + cc*100 + bb*10 + aa;
            end
      end
    end
end
toc
disp('此代码使用matlab编程')
disp(['Problem36所用时间为： ',num2str(toc),'秒'])
disp(['Problem36的答案为： ',num2str(Output)])

Trami 发表于 2018-9-25 16:38:54

本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:36 编辑

import time
start = time.time()

c = []
for i in range(1, 1000000):
    binary = bin(i)
    binary = str(binary)
    i = str(i)

    if i == i[::-1] andbinary == binary[::-1].replace('b0', ''):
      c.append(i)
print(sum(map(int, c)))

end = time.time()
print(end - start)

用时0.703022956848

k往事如烟k 发表于 2019-3-27 16:53:10

numList = []

for num in range(1000000):
    decNumList = list(str(num))
    decNumTempList = list(str(num))
    binNumList = list(str(bin(num)))
    binNumTempList = list(str(bin(num)))
    decNumTempList.reverse()
    binNumTempList.reverse()
    if decNumList == decNumTempList:
      if binNumList == binNumTempList:
            numList.append(num)

print(sum(numList))872187

王小召 发表于 2019-6-13 16:39:59

送分题：872187

print(sum(num for num in range(1, 1000000) if str(num) == str(num)[::-1] and str(bin(num)).split('b') == str(bin(num)).split('b')[::-1]))

永恒的蓝色梦想 发表于 2020-4-18 22:31:53

本帖最后由 永恒的蓝色梦想 于 2020-5-9 13:14 编辑

C++ 44ms#include<iostream>
using namespace std;


int main() {
    int i, j, res = 0, sum = 0;

    for (i = 1; i < 1000000; i++) {
      j = i;

      while (j) {
            res = (res << 1) | (j & 1);
            j >>= 1;
      }

      if (res == i) {
            while (res) {
                j = j * 10 + res % 10;
                res /= 10;
            }

            if (j == i) {
                sum += i;
            }
      }
      else {
            res = 0;
      }
    }

    cout << sum << endl;
    return 0;
}

debuggerzh 发表于 2020-8-5 16:36:57

872187

Process returned 0 (0x0)   execution time : 0.321 s
Press any key to continue.
利用vector判断回文串
#include<iostream>
#include<vector>
using namespace std;

const int M = 1e6;
vector<int> decimal;
vector<int> bin;

bool judge(int x,int base,vector<int> & v){
while(x){
    v.push_back(x % base);
    x /= base;
}
int len = v.size();
for (int i = 0;i < v.size()/2;i++)
    if (v != v) return false;

return true;
}

int main(){
int ans = 0;
for (int i = 1;i < M;i++){
    decimal.clear();
    bin.clear();
    if (judge(i,10,decimal) && judge(i,2,bin))ans += i;
}
cout << ans << endl;
return 0;
}

a1351468657 发表于 2021-3-16 19:22:23

#include <stdio.h>
#include <string.h>
#include <math.h>

void reverse(char str[], char rts[]);
void Dec2bin(int, char []);

void reverse(char str[], char rts[])//回文
{
        int i, j, k;
        k = strlen(str);

        for (i = 0, j = k - 1; i < k; i++, j--)
        {
                rts = str;
        }
        rts = '\0';
}
void Dec2bin(int num, char bin[])//十进制转二进制
{
        int i = 0, j, k;
        j = num;
        while (j)
        {
                k = j % 2;
                bin = k + '0';
                j /= 2;               
        }
        bin = '\0';

}
main()
{
        char str, rts, bin;
        int i, j, k, len, flag = 1, sum = 0;

        for (i = 1; i < 1000000; i += 2) //由于要二进制回文后也相等，所以只能是偶数
        {
                sprintf(str, "%d", i);
                reverse(str, rts);
                k = atoi(rts);
                if (k == i)
                {
                        Dec2bin(i, bin);
                        reverse(bin, rts);
                        len = strlen(bin);
                        for (j = 0; j < len; j++)
                        {
                                if (bin != rts)
                                {
                                        flag = 0;
                                        break;
                                }
                        }
                        if (flag)
                        {
                                sum += i;
                                printf("%d ", i);
                        }
                        flag = 1;
                }       
        }
        printf("\n%d\n", sum);
}

答案为：
1 3 5 7 9 33 99 313 585 717 7447 9009 15351 32223 39993 53235 53835 73737 585585

总和为：872187

B1tetheDust 发表于 2022-10-24 15:22:55

import time as t

start = t.perf_counter()
palindromic_nums = []
for num in range(1000000):
    num_str = str(num)
    num_bin = str(bin(num)).lstrip('0b')
    if num_str == num_str[::-1] and num_bin == num_bin[::-1]:
      palindromic_nums.append(num)

print(palindromic_nums)
print(sum(palindromic_nums))
print("It costs %f s" % (t.perf_counter() - start))

mathtimes 发表于 2023-10-15 11:45:17

结果
$ time ./main
872187

real        0m0.004s
user        0m0.004s
sys        0m0.000s

两个判断回文的函数
fn palindrome(x: u32) -> bool {
    let mut x = x;
    let bits: &mut = &mut ;
    let mut i: usize = 0;
    while x != 0 {
      bits = (x % 10) as u8;
      i += 1;
      x /= 10;
    }
    for j in 0..=i / 2 {
      if bits != bits {
            return false;
      }
    }
    true
}

fn palindrome2(x: u32) -> bool {
    let len = u32::BITS - x.leading_zeros();
    for j in 0..len / 2 {
      if ((x >> j) ^ (x >> (len - 1 - j))) & 1 != 0 {
            return false;
      }
    }
    true
}

#
mod tests {
    use super::*;
    #
    fn test_palindrome() {
      assert!(palindrome(123321));
      assert!(palindrome(12321));
      assert!(!palindrome(2321));
      assert!(palindrome(1));
      assert!(palindrome(585));
    }
    #
    fn test_palindrome2() {
      assert!(palindrome2(0b101101));
      assert!(palindrome2(0b101));
      assert!(!palindrome2(0b1010));
      assert!(palindrome2(0b1));
      assert!(palindrome2(585));
    }
}
主程序
fn main() {
    let mut sum = 0;
    for i in 1..1e6 as u32 {
      if palindrome2(i) && palindrome(i) {
            sum += i;
      }
    }
    println!("{sum}");
}

查看完整版本: 题目36：求出100万以下所有十进制和二进制表示都是回文的数字之和