回文数

[编程题]回文数

热度指数：5563 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。

又如：对于10进制数87：

STEP1：87+78 = 165 STEP2：165+561 = 726

STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2<=N<=10，N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”

输入描述:

两行，分别为N,M

输出描述:

STEP=ans

示例1

输入

9
87

输出

STEP=6

算法知识视频讲解

keepyang

package main

import (
    "fmt"
    "strconv"
)

func reverse(s string) string {
    str := ""
    for _, k := range s {
        str = string(k) + str
    }
    return str
}
func toDecimal(s string, n int) int {
    res, length, cur := 0, len(s), 1
    for i := length - 1; i >= 0; i-- {
        if s[i] <= '9' {
            res += int(s[i]-'0') * cur
        } else if s[i] <= 'Z' {
            res += (int(s[i]-'A') + 10) * cur
        } else {
            res += (int(s[i]-'a') + 10) * cur
        }
        cur *= n
    }
    return res
}
func main() {
    var (
        n int    // 进制数
        m string // 数
    )
    fmt.Scan(&n, &m)
    for i := 1; i <= 30; i++ {
        rm := reverse(m)
        m10, rm10 := toDecimal(m, n), toDecimal(rm, n)
        m = strconv.FormatInt(int64(m10+rm10), n)
        if reverse(m) == m {
            fmt.Printf("STEP=%d", i)
            return
        }
    }
    fmt.Println("Impossible!")
}

发表于 2023-12-23 04:13:15 回复(0)