题目4：找出由两个三位数乘积构成的回文

永恒的蓝色梦想

def reverse(n):
    res=0
    while n:
        res=res*10+n%10
        n//=10
    return res

max=0

for i in range(100,1000):
    for j in range(100,1000):
        j*=i
        if j>max and reverse(j)==j:
            max=j

print(max)

RRRex

#include <stdio.h>
#include <time.h>


int main()
{
    int begin_time, end_time;
    begin_time = clock();

    int i, j, num, temp[7], index, length, flag = 0, biggest;
    for (i = 100; i < 999; i++)
    {
        for (j = i; j < 999; j++)
        {
            num = i * j;
            for (index = 0; num; index++)
            {
                temp[index] = num % 10;
                num = num / 10;
            }
            length = index - 1;
            for (index = length; index >= 0; index--)
            {
                if (temp[index] == temp[length-index])
                {
                    flag = 1;
                }
                else
                {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)
            {
                biggest = i * j;
                printf("%d = %d * %d\n", biggest, i, j);
            }
        }
    }

    end_time = clock();
    printf("\n程序一共运行%dms\n", end_time - begin_time);

    return 0;
}

justjust001

#include <stdio.h>

int main()
{
        int begin = clock();
        char p[10];
        int num = 0;
        int x, y, len, i, j;


        for (x = 100; x < 1000; x++)
                for (y = 100; y < 1000; y++)
                        if (x * y > num)
                        {
                                itoa(x * y, p, 10);
                                if ((len = strlen(p)) % 2 == 0)                //数字个数必须为偶数
                                {
                                        for (i = 0, j = len - 1; i < j; i++, j--)
                                                if (p[i] != p[j])
                                                        break;
                                        if (i > j)
                                                num = x * y;
                                }
                        }
                
        printf("最大的有由个三位数乘积构成的回文数 = %d\n", num);
        int end = clock();
        printf("time = %dms\n", end - begin);
        system("pause");
        return 0;
}

华博文

import time

def pan(nu):
    pas = "pas"
    wen = str(nu)
    yuan = 0
    for each in range(1 , len(wen) // 2 + 1):
        if wen[yuan - 1 + each] != wen[yuan - each]:
            #print("fir  " + wen[yuan + each])
            #print("sec  " + wen[yuan - each])
            #print(wen)
            pas = "!="
            break
   
    return pas
    

def run():
    zidian = dict()
    for fir in range(999 , 100 , -1):
        for sec in range(999 , 100 , -1):
            result = fir * sec
            gui = pan(result)
            if gui == "pas":
                zidian[result] = [fir , sec]
                #return fir , sec , result

    return zidian

time_start = time.perf_counter()
form = run()
miao = time.perf_counter() - time_start

print("最大回文数为：{}\n由{} * {}构成\n运行时间为：{:.2f}秒 由|-- Clownc --|提供~~".format
      (max([each for each in form]) , form[max([each for each in form])][0] , form[max([each for each in form])][1] , miao))

            

1666194196

#include <stdio.h>
void main(){
        //回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = 91 × 99。
        //找出由两个3位数相乘得到的最大回文乘积。
        int i,j,max=0,x,y;//两个三位数 i,j;最大回文数max,回文数的因数x,y 
        long chengji;//i*j的乘积 
        for(i=100;i<1000;i++){//i：100开始到999 
                for(j=100;j<1000;j++){//j：100开始 到999 
                        chengji=i*j; //i=100 *j从100到999；i=101 *j从100到999；  循环899*899次 
                        if(chengji>max){        
                                if(chengji>100000){//最大的肯定在6位数中 
                                        int ge;
                                        ge = chengji%10;//拿出个位这个数 
                                        int shi;
                                        shi = chengji/10%10;//拿出十位这个数 
                                        int bai;
                                        bai = chengji/100%10;//拿出百位这个数 
                                        int qian;
                                        qian = chengji/1000%10;//拿出千位这个数 
                                        int wan;
                                        wan = chengji/10000%10;//拿出万位这个数 
                                        int shiwan;
                                        shiwan = chengji/100000;//拿出十万位这个数 
                                        
                                        if(ge==shiwan&&shi==wan&&bai==qian){//回文特征：第一位与最后一位相等，第二位与十位相等... 
                                                printf("回文数=%d\n",chengji);
                                                max = chengji;   //把最后一个（最大的）赋给max，两个因数给x，y 
                                                x = i;                        
                                                y = j;
                                        }
                                                
                                }
                        }        
                }
        }
        printf("\n");
        printf("最大回文数为:%d\n这两个三位数为:%d、%d",max,x,y);//循环外面 输出这些数 
}

带上面具的孩纸

#include <stdio.h>
#include <stdlib.h>

int IsPalindrome()
{
    int i,j;
    int count;
    int Temp = 0;//临时存放回文数
    int Palindrome;
    int MAX = 0;

    for(i = 100;i < 1000;i++)
    {
        for(j = 100;j < 1000;j++)
        {
            count = i * j;

            Palindrome = count;

            while(count != 0)
            {
                Temp = Temp * 10 + count % 10;
                count /= 10;
            }

            if(Palindrome == Temp)
            {
                if(MAX < Temp)
                {
                    MAX = Temp;
                }
            }
            Temp = 0;
        }
    }
    return MAX;
}

int main(void)
{
    int Palindrome;//回文数

  Palindrome = IsPalindrome();

  printf("%d\n",Palindrome);

  system("pause");

    return 0;
}

guoquanli

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//判断一个数是回文数字
bool IsPaLindrome(int n){
    if( n > 998001){
        return false;
    }
    if( n >= 10000 && n < 100000){
        int a[5] = {0};
        int Index = 0;
        int value = 0;
        while(n != 0){
            value = n%10;
            a[Index++] = value;
            n = n/10;
        }
        for(int i = 0; i<3 ; i++){
            if(a[i] != a[4-i]){
                return false;
            }
        }
        return true;
    }else{
        int a[6] = {0};
        int Index = 0;
        int value = 0;
        while(n != 0){
            value = n%10;
            a[Index++] = value;
            n = n/10;
        }
        for(int i = 0; i<3 ; i++){
            if(a[i] != a[5-i]){
                return false;
            }
        }
        return true;
    }
}
void main(){
    int result = 0;
    int a,b;
    for(int i = 100; i<1000; i++){
        for(int j = 100; j<1000; j++){
            if(IsPaLindrome(i*j)){
                if(i*j >result){
                    result = i*j;
                    a = i;
                    b = j;
                }
            }
        }
    }
    printf("finally value is %d[%d,%d]\n",result,a,b);
    return;
}

==================================================
finally value is 906609[913,993]

代号-K

经过了几个小时的努力，终于想出了最优的方法
1: 9 = 1 * 9
2: 9009 = 91 * 99
3: 906609 = 913 * 993
4: 98100189 = 9811 * 9999
5: 2811991182 = 34034 * 82623
6 位之后电脑不支持了

#define BIT_FLAG 5
#define BIT_MAX  (BIT_FLAG+1)*2 - 1
#define BIT_MIN  BIT_FLAG*2 - 1
#define MAX_NUM 9
void getHuiWen(int k, int *array, int m, ElementType *result)
{
    int n = k - 1 - m;
    if(m <= n)
    {
        int i;
        for(i = 1; i <= MAX_NUM; i++)
        {
            array[m] = i;
            array[n] = i;
            int j = 0;
            ElementType sum = 0;
            while( j < k)
            {
                //printf("%d", array[j]);
                sum += array[j]*int(pow(10,k-j-1));
                j++;
            }
            // optimization
            if(*result >= sum)
            {

                if(*result >= sum * 10)
                {
                    return;
                }
                continue;
            }
            j = int (pow(10, BIT_FLAG - 1));
            while(j <= int (pow(10, BIT_FLAG) - 1))
            {
                if(sum % j == 0)
                {
                    //printf("%d\n", sum);
                    int ret;
                    ret = (sum / j) / int (pow(10, BIT_FLAG - 1));
                    if(ret > 0 && ret < 10)
                    {
                        ret = sum / j;
                        printf("%lld = %d * %d\n", sum, j, ret);
                        *result = sum;
                        break;
                    }

                }
                j++;
            }

            //clear numbers in middle
            if(i == MAX_NUM)
            {
                j = 1;
                while( j < k-1)
                {
                    array[j] = 0;
                    j++;
                }
            }
            //ecursive
            getHuiWen(k, array, m+1, result);
        }
    }
}

int main(int argc, char *argv[])
{
    int k = BIT_MAX;
    int array[BIT_MAX] = {0};
    ElementType ret = -1;
    for(; k >= BIT_MIN; k--)
    {
        getHuiWen(k, array, 0, &ret);
    }
    //int sum = calculateCircle();
    printf("%lld\n",ret);
    return 0;
}

永恒的蓝色梦想

C++ 6ms

#include<iostream>
using namespace std;


int main() {
    int i, j, k, temp, reversed, res = 0;

    for (i = 100; i < 1000; i++) {
        for (j = 100; j < 1000; j++) {
            if ((k = i * j) > res) {
                reversed = 0;
                temp = k;

                while (temp) {
                    reversed = reversed * 10 + temp % 10;
                    temp /= 10;
                }

                if (reversed == k) {
                    res = k;
                }
            }
        }
    }

    cout << res << endl;
    return 0;
}

leon0149

C 0.018 s

#include <stdio.h>
#include <time.h>

int reverse(int);
void compare(void);

int reverse(int num) {
    int completed = 0;
    do
    {
        completed = (num % 10) + completed * 10;
        num /= 10;
    }while(num);
    return completed;
}

void compare(void)
{
    int i, j;
    int max = 0;
    int temp;
    int o, p;
    for (i = 0; i < 1000; i++) {
        for (j = 0; j < 1000; j++) {
            if (i * j == reverse(i * j)) {
                temp = i * j;
                if (max < temp){
                    max = temp;
                    o = i;
                    p = j;
//                    printf("%d * %d = %d\n", o, p, max);
                }
            }
        }
    }
    printf("%d * %d = %d\n", o, p, max);
}

int main(void) {
    clock_t start, finish;
    double duration;
    start = clock();
    compare();
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    putchar('\n');
    printf("%.3f", duration);
    return 0;
}

leon0149

def isPalindrome(x):
    x = str(x)
    return x == x[::-1]


max = 0

for i in range(999, 99, -1):
    for j in range(999, 99, -1):
        num = i * j
        if isPalindrome(num):
            max = num if max < num else max

print(max)

永恒的蓝色梦想

leon0149 发表于 2020-5-7 14:21

你的程序有很明显的问题。
你的程序中计算了1000与其他数的积，没有计算100与其他数的积，得出正确答案纯属运气。

leon0149

永恒的蓝色梦想 发表于 2020-5-7 14:43
你的程序有很明显的问题。
你的程序中计算了1000与其他数的积，没有计算100与其他数的积，得出正确答案 ...

ok  没注意 谢谢指正

数据小随从

#include<stdio.h>
#include<stdlib.h>
#include<time.h>


int isprime(int num)
{
        int i;
        for (i = 2; i < num; i++)
        {
                if (num%i == 0)
                        break;
        }
        if (i >= num)
                return 1;
}


void main()
{
        double start, finish;
        int j;
        long long sum = 0;
        start = clock();
        for (j = 2; j < 200000; j++)
        {
                if (isprime(j) == 1)
                {
                        sum += j;
                }
        }
        finish = clock();
        printf("两百万以内的质数和为 = %lld\n", sum);
        printf("\n耗时%lf s\n", (finish - start)/CLOCKS_PER_SEC);
        system("pause");
}

输出为：二十万以内的质数和为 = 1709600813

耗时8.616000 s
百万耗时太长，输出了二十万的结果

KingFish-v-

答案是993*913=906609，用时0.01s左右。

找4位数x4位数的最大回文用时也在0.01s内，5位数x5位数用时0.58s，6位数0.37秒，7位数一百万到一千万用了143秒（应该这种情况就需要更好的算法了）。

import time
starttime = time.time()
##########################用时检测##################
#回文检测函数就是最普通地把数字变成列表然后翻转进行比较
#思路的话是生成两个倒过来的列表（100-1000变为1000-100），从大到小检测
#然后每次一个循环后把列表中的第一个数字去掉，因为已经计算过一次了
#当出现回文时停止该循环，同时把列表中第二个列表中比当前数字小的都去掉
#因为比第二个乘数小但是第一个乘数大的可能性都检测过了
#接下来继续循环，每当乘积小于已经存在的回文时就进入下一个循环
#当第一个列表中第一个数字比第二个列表中最后一个数字小的时候就不可能出现更大的回文了


def check(number):                          #回文检测函数
    result = list(str(number))              
    result2 = result[:]
    result2.reverse()
    if result == result2:
        resultlist.append(number)
        return True
    else:
        return False

def startfunc(list1, list2):                
    for each in list2:
        result = list1[0] * each
        if result < resultlist[-1]:         
            break
        if check(result):
            resultequation.append(str(list1[0])+"*"+str(each)+"="+str(result))  #将乘法式加入对应列表
            list2 = list2[0:(list2.index(each)+1)]      #把列表2中比当前数字小的都切片切掉
            listB.clear()
            listB.extend(list2)         #清空原先的列表2并将切片后的列表放进去
            break
        
resultlist = [0]                        #列表装符合要求的乘积
resultequation = []                     #列表装符号要求的乘积的乘法式

'''这里设定数字范围'''
listA = list(range(100,1000))         
listB = list(range(100,1000))

listA.reverse()
listB.reverse()


while listA[0] > listB[-1]:             #此时不可能出现更大的乘积了，循环结束
    startfunc(listA,listB)
    listA.pop(0)                        #去掉两个列表中的第一个数字（已经算过）
    listB.pop(0)

print(resultequation[-1])

##############################################
endtime = time.time()
print(endtime - starttime)

永恒的蓝色梦想

代号-K 发表于 2020-3-12 15:46
经过了几个小时的努力，终于想出了最优的方法
1: 9 = 1 * 9
2: 9009 = 91 * 99

99979 * 99681 = 9966006699

永恒的蓝色梦想

KingFish-v- 发表于 2020-8-10 21:44
答案是993*913=906609，用时0.01s左右。

找4位数x4位数的最大回文用时也在0.01s内，5位数x5位数用时0.58 ...

不错，我也学习一下

yhhpf

a = 1000
b = 1000
l1 = []
while a > 99:
    a -= 1
    b = 1000
    while b >99:
        b -= 1
        s = a*b
        c = list(str(s))
        i = len(c)
        x = 1
        while x <= int(i/2) :
            if c[x-1] != c[0-x]:
                break
            if x == int(i/2):
                l1.append(s)
                break
            x += 1
print(max(l1))

基本解法，忙完回头看~~~

a315734685

# 一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是 9009 = 91 * 99。
# 找出最大的有由个三位数乘积构成的回文数。
def huiwen(x):
    y = str(x)[::-1]
    if int(y) == x:
        return True
    else:
        return False

max_Num = 0
for i in range(100, 999):
    for j in range(100, 999):
        x = j * i
        if huiwen(x):
            if max_Num < x:
                max_Num = x

print(max_Num)

有马_冬巳

'''一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是 9009 = 91 * 99。
找出最大的由两个三位数的乘积构成的回文数。'''

palindrome = []

def ispalindrome(num):
    s = str(num)
    a = 0
    b = len(s)-1
    check = 0
    for i in range(int((len(s)/2))):
        if len(s) % 2 != 0:
            return False
        if s[a] != s[b]:
            if check == 0:
                check += 1
            if check != 0:
                break
        a += 1
        b -= 1
    if check == 0:
        return True

def multiply(num1,num2):
    for number1 in range(num1, 99, -1):
        for number2 in range(num2, 99, -1):
            number = number1*number2
            if ispalindrome(number):
                palindrome.append([number1, number2, number])

def getbiggestpalindrome():
    temp = 0
    re = 0
    for i in range(len(palindrome)-1):
        if temp < palindrome[i][2]:
            temp = palindrome[i][2]
            re = i
    print(palindrome[re])

start_palindrome = time.time()
multiply(999,999)
getbiggestpalindrome()
time_palindrome = time.time() - start_palindrome
print("%f秒" %time_palindrome)

[993, 913, 906609]
0.712786秒