پاسخ سوال مساله هالت کوئرا

پاسخ سوال مساله هالت کوئرا

در این نوشته تمرین “مساله هالت” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال مساله هالت کوئرا

دوره 1028 ایا، دوره 28 ایا را بسیار خفن می‌پنداشتند (زیرا دوره 28 ایا واقعا خفن بودند). اعتقاد دوره 1028 ایا به خفونت دوره 28 ایا چنان بود که فکر می‌کردند دوره 28 ایا می‌توانستند حتی مساله توقف را حل کنند! مساله توقف (به انگلیسی: Halting problem) مطرح می‌کند که آیا می‌توان برنامه‌ای نوشت که یک برنامه از ورودی بگیرد و تعیین کند که آیا برنامه متوقف می‌شود یا خیر. ثابت شده که در حالت کلی، الگوریتمی برای حل این مساله وجود ندارد. مسئول دوره 1028 ایا برای اینکه اعتماد به نفس دوره 1028 ایا تقویت شود، نسخه ساده شده‌ای از مساله هالت را به آن‌ها داد تا آن‌ها فکر کنند مثل دوره 28 ایا خفن هستند. در این نسخه‌ ساده شده سه نوع دستور موجود است:

assign a = b + c
cout a
goto l

که در آن $a$ و b و c یک حرف کوچک انگلیسی (که نام یک متغیر است) یا یک عدد یک رقمی هستند و $l$ شماره خطی از برنامه است. تضمین می‌شود که بعد از assign متغیر a همیشه یک حرف کوچک انگلیسی است. شما باید خط به خط برنامه را دنبال کنید، در صورتی که برنامه پایان‌ناپذیر است، $-1$ را چاپ کنید. در غیر این‌صورت خروجی این برنامه را چاپ کنید. در این برنامه cout به معنای چاپ کردن یک عدد یا یک متغیر است. goto به معنای پرش به یک خط خاص است (خط‌ها از ۱ شماره‌گذاری شده‌اند). assign a= b + c یعنی b+c را در متغیر a قرار بده. هر حرف کوچک انگلیسی نشان‌ دهنده یک متغیر است و محتوای همه‌ متغیرها در ابتدا صفر است. با توجه به اینکه جواب مسئله ممکن است بزرگ شود شما باید باقی مانده خروجی بر 10^9+7109+7 را بگویید.

ورودی سوال مساله هالت

در ورودی یک برنامه به شما داده می‌شود. در خط اول n تعداد خط‌های برنامه و در n خط بعد در هر خط یک دستور از برنامه داده می‌شود.

$$1\le l\le n\le 100000$$

خروجی سوال مساله هالت

اگر برنامه داده‌شده تمام نمی‌شود، در تنها سطر خروجی $-1$ چاپ کنید. در غیر اینصورت خروجی‌های برنامه‌ (به ازای هر cout) را چاپ کنید.

حل سوال مساله هالت

x = int(input())
list1 = []

for i in range((int)(x)):
    list1.append(input())



variables = {}
outputs = []
line = 0
tekrar = []
for i in range(x):
    tekrar.append(0)
flag = False
while(True):
    aKhat = list1[line].split(" ")
    tekrar[line] += 1
    if(tekrar[line] > 1):
        flag = True
        print(-1)
        break
    if(aKhat[0] == "assign"):
        aval = aKhat[3]
        dovom = aKhat[5]
        if(not aval.isdigit()):
            if(not aval in variables):
                variables[aval] = 0
            aval = variables[aval]
        if(not dovom.isdigit()):
            if(not dovom in variables):
                variables[dovom] = 0
            dovom = variables[dovom]
        variables[aKhat[1]] = (int(aval) + int(dovom)) % 1000000007
    elif(aKhat[0] == "cout"):
        adad = aKhat[1]
        if(not adad.isdigit()):
            if(not adad in variables):
                variables[adad] = 0
            adad = variables[adad]
        outputs.append(adad)

    if(aKhat[0] == "goto"): #elif to if
        line = int(aKhat[1]) -1
    else: #added7
        line += 1 #added
    if(line >= x):#added
        break       #added

if(not flag):
    for i in outputs:
        print(i)

منبع سوال‌: وب‌سایت کوئرا

اگر روش حل بهتری برای “تمرین مساله هالت” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم. اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.