Python 3.7

프로그램 내에서 2배, 리버스의 적용 순에 따라 결과가 다르게 나타날 수도 있겠습니다.

def _progress(num: int):  # num에 대해 2배, 리버스 계산 튜플 반환
    reversed_num = 1
    if num >= 10:
        strnum = str(num)
        strnum = strnum[-1] + strnum[1:-1] + strnum[0]
        reversed_num = int(strnum)
    return num * 2, reversed_num


def _find_routes(target: int):
    routes = {1: ""}
    while target not in routes:  # 목표 정수가 routes에 없을 경우
        tmpdic = {}
        for k in routes:  # routes 내 키(정수)에 대해 2배, 리버스 수행
            dbl, swp = _progress(k)
            if dbl not in routes and dbl not in tmpdic:
                tmpdic[dbl] = routes[k] + "D"
            if swp not in routes and swp not in tmpdic:
                tmpdic[swp] = routes[k] + "R"
        routes.update(tmpdic)  # 중복 키를 제외한 사전을 추가하여 routes 갱신
    return routes[target]


def get_routes(target):  # 1 -> num까지 도달하는 과정 출력
    routes = _find_routes(target)
    result = [1]
    for c in routes:
        # 'D': 2배, 'R': 리버스
        addval = result[-1] * 2 if c == "D" else _progress(result[-1])[1]
        result.append(addval)
    return "->".join(str(i) for i in result)


def main():
    result = get_routes(77)
    print(result)
    result = get_routes(757)
    print(result)


if __name__ == "__main__":
    main()

1->2->4->8->16->32->64->128->256->652->1304->2608->5216->6215->12430->24860->49720->9724->19448->38896->77792->27797->55594->45595->91190->1199->9191->18382->28381->56762->26765->53530->3535->7070->77

1->2->4->8->16->61->122->244->488->976->679->1358->8351->16702->26701->53402->106804->213608->427216->627214->1254428->2508856->5017712->2017715->4035430->35434->45433->90866->181732->281731->563462->263465->526930->26935->53870->3875->7750->757

python 3.6

def dict_generator(key, value, width=5):
    if key % 10 == 0:
        return {key//2: value+'D'}
    else:
        temp_dict = {}
        if key % 2 == 0:
            temp1 = key//2
            temp_dict[temp1] = value+'D'
        for i in range(width):
            temp2 = '0'*i + str(key)
            temp2 = int(temp2[-1]+temp2[1:-1]+temp2[0])
            temp_dict[temp2] = value+'R'
        return temp_dict


def check_dict(dict, depth=1, max_depth=100, num_limit=100000000):
    print(depth)
    print(list(dict.keys())[-1], list(dict.values())[-1])
    if 1 in dict:
        return dict[1][::-1]
    if depth == max_depth:
        return None
    else:
        temp_dict = {}
        for key, value in dict.items():
            if value[-3:] != 'RRR':
                temp_dict.update(dict_generator(key, value))
        temp_dict = {k: v for k, v in temp_dict.items() if k not in dict.keys() and k < num_limit}
        return check_dict(temp_dict, depth+1)


print(check_dict(dict_generator(77, '')))

77의 경우 'DDDDDDDRDRDRDDDDDRRDDDRDDRDRDRDRDR' 입니다.

757의 경우 'DDDDRDDDDRDRDRDDDDRDDDRDRRDDRDRDRDRDR' 입니다.

width, max_depth, num_limit의 경우 충분히 큰 숫자를 넣어주었습니다.

#include<cstdio>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
int memory[10000000];
int num_lenght(int num) {
    int temp=1;
    while (temp && num/temp > 10)
    {
        temp*=10;
    }
    return temp;
}

void main()
{
    int n;
    cin >> n;
    queue<int> q;
    q.push(1);
    memory[1] = 1;
    while (!q.empty() && !memory[n])
    {
        int temp = q.front();
        q.pop();

        if (temp * 2 < 10000000 && !memory[temp*2] )
        {
            memory[temp*2] = temp;
            q.push(temp * 2);
        }
        int temp_num = 
            temp % num_lenght(temp) 
            - temp % 10
            + temp / num_lenght(temp)
            + temp % 10 * num_lenght(temp);
        if (temp_num < 10000000 && !memory[temp_num])
        {
            memory[temp_num] = temp;
            q.push(temp_num);
        }
    }
    stack<int> s;
    int temp=n;
    while (temp != 1)
    {
        s.push(temp);
        temp = memory[temp];
    }
    cout << 1 << "\t";
    while (!s.empty()) {
        cout << s.top()<<"\t";
        s.pop();
    }
}

1 2 4 8 16 32 64 128 256 652 1304 2608 8602 17204 34408 68816 137632 275264 550528 850525 1701050 701051 101057 71060 1067 770 77

1 2 4 8 16 61 122 244 488 976 679 1358 8351 16702 26701 53402 106804 213608 427216 627214 1254428 2508856 5017712 2017715 4035430 35434 45433 90866 181732 281731 563462 263465 526930 1053860 53870 107740 7750 757

include

include

include

include

using namespace std; int memory[10000000]; int num_lenght(int num) { int temp=1; while (temp && num/temp > 10) { temp*=10; } return temp; }

void main() { int n; cin >> n; queue q; q.push(1); memory[1] = 1; while (!q.empty() && !memory[n]) { int temp = q.front(); q.pop();

    if (temp * 2 < 10000000 && !memory[temp*2] )
    {
        memory[temp*2] = temp;
        q.push(temp * 2);
    }
    int temp_num = 
        temp % num_lenght(temp) 
        - temp % 10
        + temp / num_lenght(temp)
        + temp % 10 * num_lenght(temp);
    if (temp_num < 10000000 && !memory[temp_num])
    {
        memory[temp_num] = temp;
        q.push(temp_num);
    }
}
stack<int> s;
int temp=n;
while (temp != 1)
{
    s.push(temp);
    temp = memory[temp];
}
cout << 1 << "\t";
while (!s.empty()) {
    cout << s.top()<<"\t";
    s.pop();
}

}

mohenjo님꺼 참고해서 만들어봤습니다

'''특이한 계산기가 하나 있다.
이 계산기에는 2배 버튼과 리버스 버튼 밖에 없다.

2배 버튼 : 숫자를 두배로 만든다.
리버스 버튼 : 숫자의 제일 앞과 제일 뒷자리수를 바꾼다.
리버스 버튼의 예)
53 -> 35
1234 -> 4231
12345 -> 52341
530 -> 35
5300 -> 305

두 개의 버튼 만으로 1에서 시작해서 77을 만들어 보시오.

추가문제 : 1에서 시작해 757을 만들어 보시오.'''
from collections import *
from time import *
def revers_button(number): #리버스 버튼 : 숫자의 제일 앞과 제일 뒷자리수를 바꾼다.
    num=list(str(number))
    num2 = ''
    if len(num)<2:
        for i in num:
            num2 += str(i)
        return int(num2)
    num[0],num[-1]=num[-1],num[0]
    for i in num:
        num2+=str(i)
    return int(num2)


def double_button(number): #두배 버튼
    return int(number*2)

def auto_process(N):

    routes={1:""}
    while N not in routes:
        dic = {}
        for number in routes:
            if double_button(number)  not in dic :
                dic[double_button(number)]=routes[number]+'D'

            if revers_button(number)  not in dic :

                dic[revers_button(number)]=routes[number]+'R'
        routes.update(dic)
    return routes
def auto_button(N):
    print('연산중...')
    pro=auto_process(N)
    print('정답: {}'.format(pro[N]))





while True:
    N=int(input('목표치: '))
    number = 1

    while True:

        print('------------------------------')
        print('1. 두배')
        print('2. 리버스')
        print('3. 정답')
        print('4. 종료')
        print('------------------------------')

        menu=input("버튼을 고르시오 (현재{0},목표{1}): ".format(number,N))

        if menu=='1':
            number=double_button(number)
        elif menu=='2':
            number=revers_button(number)
        elif menu=='3':
            auto_button(N)
            break
        elif menu=='4':
            break
        if number==N:
            print('Clear!!')
            break

    menu2=input('종료 하시겠습니까?y/n: ')
    if menu2=='n':
        continue
    else:
        break

C#

class Program
    {
        static int Twice(int a)
        {
            return a * 2;
        }

        static int Revers(int b)
        {
            string str = b.ToString();
            char[] str_s = str.ToCharArray();
            string rev_str = "";

            if (str.Length == 1)
                return b;

            rev_str = str_s[str.Length - 1].ToString();
            for (int i = 1; i < str.Length - 1; i++)
            {
                rev_str = rev_str + str_s[i].ToString();
            }
            rev_str = rev_str + str_s[0].ToString();

            return int.Parse(rev_str);
        }

        static void Main(string[] args)
        {
            int target = 0;
            int b = 1;
            Random r = new Random();
            string step = "";

            Console.Write("target number : ");
            target = int.Parse(Console.ReadLine());

            while (b != target)
            {
                if (r.Next(0,2) == 0)
                {
                    b = Twice(b);
                    step = step + "T" + b.ToString() + " ";
                } else
                {
                    b = Revers(b);
                    step = step + "R" + b.ToString() + " ";
                }

                if (b > 10000000)
                {
                    b = 1;
                    step = "";
                }
            }
            Console.WriteLine("SUCCESS!!");
            Console.WriteLine(step);
        }
    }

아직 전체 탐색에 대해서도 깊게 공부하지 못한 초보라, 나름 궁리한 것이 리스트를 이용한 탐색이었는데, 조악하기도 하고 시간이 너무 오래 걸려 답이 나올 생각을 하지 않습니다. 코드는 아래와 같습니다.

def CAL(res, path) :
    RES1, rin, path_1, dou, rev = [], [], [], 0, 0
    for i in res :

        dou = i*2

        if not dou in RES1 :
            if dou in res :
                RES1.append(dou)
                path_1.append(path[res.index(dou)])

            else :
                RES1.append(i*2)
                path_1.append(path[res.index(i)] + "D")

        pos_lin = str(i)
        if len(pos_lin) == 1 :
            pos_lin = pos_lin
        else :
            pos_lin = int(pos_lin[-1]+pos_lin[1:-1]+pos_lin[0])

        if not pos_lin in RES1 :

            if pos_lin in res :
                RES1.append(pos_lin)
                path_1.append(path[res.index(pos_lin)])
            else : 
                RES1.append(pos_lin)
                path_1.append(path[res.index(i)] + "R")
    return RES1, path_1

def REP(g, p, c) :
    a, b = CAL(g, p)
    if 77 in a :
        print(b[a.index(77)], a.index(77))
    else :
        return REP(a, b, c+1)

REP([1], [''], 0)

중간 과정을 출력하도록 해서 다른 분들이 올린 코드의 출력들과 비교해 봤는데, 출력이 같거나 비슷한 걸로 봐서는 계산 자체가 틀린 것 같지는 않고, 제 코드가 너무 비효율적이라는 판단에 도달했습니다. 사실 리스트로 코드를 짠 이유도 단순히 딕셔너리 자료형에 익숙하지 않았던 탓이 있었는데, 공부를 게을리 한 결과가 나타난 것 같네요. 그래서 mohenjo님의 코드를 보면서(송구스럽게도 거의 그대로 옮겨놓은 수준입니다.) 딕셔너리 자료형을 활용하여 만들어본 것이 아래 코드인데, 답이 아주 빠르게 구해졌습니다.

def rev(r) :
    if r < 10 :
        return r
    else :
        r = str(r)
        return int(r[-1]+r[1:-1]+r[0])

def cal(res, ob) :
    while not ob in res :
        pre_res = {}
        for n in res :
            rev_n, doub_n = rev(n), 2 * n
            if not rev_n in res :
                pre_res[rev_n] = res[n] + 'R'
            if not doub_n in res :
                pre_res[doub_n] = res[n] + "D"
        res.update(pre_res)
    return ob, res[ob]


RES = {1 : ''}
OBJ = 77
print(cal(RES, OBJ))

결과

(77, 'DDDDDDDDRDDDRDDDRDDDRDRDRRDRDRDRDR')

아래는 위의 계산이 맞는지 확인하기 위해서 1부터 계산을 해본 결과입니다.

- 2 - 4 - 8 - 16 - 32 - 64 - 128 - 256 - 652 - 1304 - 2608 - 5216 - 6215 - 12430 - 24860 - 49720 - 9724 - 19448 - 38896 - 77792 - 27797 - 55594 - 45595 - 91190 - 1199 - 9191 - 18382 - 28381 - 56762 - 26765 - 53530 - 3535 - 7070 - 77

Python 3.7.4에서 작성했습니다

class Calculator :
    def __init__(self) :
        self.__list = {}
        self.__current = {1 : ''}

    def double(self, num) :
        return num * 2

    def reverse(self, num) :
        num = str(num)
        return int(num[len(num) - 1] + num[1:len(num) - 1] + num[0])

    def calculate(self, dest) :
        while True :
            self.__temp = {}
            for current in self.__current :
                self.__temp[self.double(current)] = self.__current[current] + 'D'
                if current > 9 :
                    self.__temp[self.reverse(current)] = self.__current[current] + 'R'

            self.__current = self.__temp
            self.__temp.update(self.__list)
            self.__list = self.__temp

            if dest in self.__current :
                print(f"{dest} is Calculated to {self.__current[dest]}")
                return

reverse_calculator = Calculator()
reverse_calculator.calculate(77)
reverse_calculator.calculate(757)

77은 DDDDDDDRDRDRDDDDDRRDDDRDDRDRDRDRDR

757은 DDDDRDDDDRDRDRDDDDRDDDRDRRDDRDRDRDRDR 입니다

77일 때는 DDDDDDDDRDDDRDDDRDDDRDRDRRDRDRDRDR,

757일 때는 DDDDRDDDDRDRDRDDDDRDDDRDRRDDRDRDRDRDR,

그리고 무한루프에 빠지지 않도록, 스텝 수에 한도를 두었습니다.

-> 3일 떄는 Steps tried exceeds 40 - given up. 을 출력

경로가 있는지 없는지를 체크하는 것은 대수학 고수께 부탁해야 되겠어요.

워낙 계산량이 많아서 ReverseNum을 최대한 효율적으로 짰습니다.

def ReverseNum(num):
    tens = 1
    while num>10*tens:
        tens *= 10
    a = int(num/tens)
    z = num%10
    return num+(z-a)*tens+a-z

def SeekPath(numTo,numGiveup):
    global SetVisited, DictToVisit
    numTried = 0
    while numTried<numGiveup:
        numTried += 1
        for num in DictToVisit.copy():
            # check if goal reached
            if num==numTo:
                return DictToVisit[num]
            # retrieve path so far
            path= DictToVisit[num]
            # add Double step
            numNext = 2*num
            if numNext not in SetVisited:
                DictToVisit[numNext] = path+'D'
                SetVisited.add(numNext)
            # add Reverse step
            numNext = ReverseNum(num)
            if numNext not in SetVisited:
                DictToVisit[numNext] = path+'R'
                SetVisited.add(numNext)
            # remove num from DictToVisit
            DictToVisit.pop(num)
    return "Steps tried exceeds "+str(numGiveup)+" - given up."

SetVisited = {1}
DictToVisit = {1:""}
print(SeekPath(77,40))

using System;
using System.Collections.Generic;

namespace solution
{
    class Program
    {
        static void Main(string[] args)
        {
            //int N = 77;
            int N = 757;

            var ans = unusualCalculator(N);
            decimal su = 1;
            Console.Write("\n1");
            for (int i = 0; i < ans.Length; i++)
            {
                if (ans[i] == 'D')
                {
                    su *= 2;                    
                }
                else
                {
                    su = reverse(su);
                }
                Console.Write("=>{0}", su);
            }

            Console.WriteLine("\n===============");
        }

        private static string unusualCalculator(int N)
        {
            Dictionary<decimal, string> dic = new Dictionary<decimal, string>();
            dic[1] = "";
            Queue<decimal> que = new Queue<decimal>();
            que.Enqueue(1);
            decimal curr = 1;
            while (true)
            {
                curr = que.Dequeue();
                decimal dSu = curr * 2;
                if (!dic.ContainsKey(dSu)) 
                {
                    dic[dSu] = dic[curr] + "D";
                    que.Enqueue(dSu);
                    if (dSu == N)
                        break;
                }
                if(curr > 10)
                {
                    dSu = reverse(curr);
                    if (!dic.ContainsKey(dSu))
                    {
                        dic[dSu] = dic[curr] + "R";
                        que.Enqueue(dSu);
                    }
                    if (dSu == N)
                        break;
                }
            }
            return dic[N];
        }

        private static decimal reverse(decimal num)
        {
            string str = "";
            str = num.ToString();
            string tmp = "" + str[str.Length - 1];
            for (int i = 1; i < str.Length - 1; i++)
                tmp += str[i];
            tmp += str[0];
            return Convert.ToDecimal(tmp);
        }
    }
}