Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7 АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…

ΠŸΡ€ΠΎΡΠΌΠΎΡ‚Ρ€ содСрТимого Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Π°
Β«ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7 АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…Β»

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7

АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…

ЦСль Ρ€Π°Π±ΠΎΡ‚Ρ‹: знакомство с основами Ρ‚Π΅ΠΎΡ€ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ Π½Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ алгоритмичСской машиной ΠŸΠΎΡΡ‚Π°.

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ обСспСчСниС: ΠΈΠΌΠΈΡ‚Π°Ρ‚ΠΎΡ€ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°

БистСма ΠΊΠΎΠΌΠ°Π½Π΄ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°: (Π²Π΅Π·Π΄Π΅ Π±ΡƒΠΊΠ²Π° n ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ Π½ΠΎΠΌΠ΅Ρ€ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΈΠ· Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния (Π½.с.) Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ (ΠΊ.с.):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π—Π°Π΄Π°Π½ΠΈΠ΅ 2
1. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚Π΅ Π½Π° машинС ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ:

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

2. ΠšΠ°ΠΊΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ Ρ€Π΅ΡˆΠ°Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ ΠΏΠΎ этой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅?

3. Π§Ρ‚ΠΎ ΠΏΡ€ΠΎΠΈΠ·ΠΎΠΉΠ΄Ρ‘Ρ‚, Ссли Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ Π²ΠΈΠ΄?

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… Π·Π°Π΄Π°Ρ‡Π°Ρ… считаСтся, Ρ‡Ρ‚ΠΎ n располоТСнных подряд ΠΌΠ΅Ρ‚ΠΎΠΊ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ число n (нСпозиционная систСма счислСния с основаниСм 1).

Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΈΠ· Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅:

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π° машинС ΠŸΠΎΡΡ‚Π°

НСдавно Π½Π° Ρ…Π°Π±Ρ€Π΅ появилось сразу Π΄Π²Π° ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Π°, посвящСнных языкам ΠΈΠ· «большой Ρ‡Π΅Ρ‚Π²Π΅Ρ€ΠΊΠΈ Ρ‚ΡŒΡŽΡ€ΠΈΠ½Π³ΠΎΠ²Ρ‹Ρ… трясин»: ΠΏΡ€ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠœΠ°Ρ€ΠΊΠΎΠ²Π° ΠΈ Brainfuck. Π”ΡƒΠΌΠ°ΡŽ, для ΠΏΠΎΠ»Π½ΠΎΡ‚Ρ‹ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½Ρ‹ Π±ΡƒΠ΄Π΅Ρ‚ интСрСсно ΡΡ€Π°Π²Π½ΠΈΡ‚ΡŒ эти эзотСричСскиС систСмы с Π΅Ρ‰Π΅ ΠΎΠ΄Π½ΠΈΠΌ Π²Π°ΠΆΠ½Ρ‹ΠΌ алгоритмичСским ΠΏΡ€ΠΈΠΌΠΈΡ‚ΠΈΠ²ΠΎΠΌ β€” машиной ΠŸΠΎΡΡ‚Π°, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ я ΠΊΠ°ΠΊ Ρ€Π°Π· занимаюсь.

Машина ΠŸΠΎΡΡ‚Π° (wiki; для простоты ΠΎΡ‚Ρ‚ΡƒΠ΄Π° ΠΆΠ΅ взят Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ синтаксиса) ΠΏΠΎΡ…ΠΎΠΆΠ° Π½Π° всСм ΠΈΠ·Π²Π΅ΡΡ‚Π½ΡƒΡŽ ΠΌΠ°ΡˆΠΈΠ½Ρƒ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°, ΠΎΠ΄Π½Π°ΠΊΠΎ ΠΎΠ±Π»Π°Π΄Π°Π΅Ρ‚ интСрСсными особСнностями. Она содСрТит лишь 6 ΠΊΠΎΠΌΠ°Π½Π΄, ΠΊΡ€ΠΎΠΌΠ΅ Ρ‚ΠΎΠ³ΠΎ, Π² ячСйки-Π±ΠΈΡ‚Ρ‹ памяти ΠΌΠΎΠ³ΡƒΡ‚ Π·Π°ΠΏΠΈΡΡ‹Π²Π°Ρ‚ΡŒΡΡ лишь 2 символа (Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ). «ЕстСствСнно», Π½ΠΈΠΊΠ°ΠΊΠΎΠΉ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ памяти, Π½Π΅ зря ΠΆΠ΅ эзотСрикой зовСтся!

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΏΡ€ΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ Π½Π° машинС ΠŸΠΎΡΡ‚Π° ΠΏΠΎΠΌΠΈΠΌΠΎ нСобходимости ΡΠΎΠ²Π»Π°Π΄Π°Ρ‚ΡŒ с оккамовским синтаксисом Π½Π°Π΄ΠΎ Π΄ΡƒΠΌΠ°Ρ‚ΡŒ ΠΎ Ρ‚ΠΎΠΌ, ΠΊΠ°ΠΊ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ Π½Π° Π»Π΅Π½Ρ‚Π΅ всС ΠΏΡ€ΠΎΠΌΠ΅ΠΆΡƒΡ‚ΠΎΡ‡Π½Ρ‹Π΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹, Π½Π΅ потСряв ΠΏΠΎ ΠΏΡƒΡ‚ΠΈ ΠΎΠ±Ρ€Π°Ρ‚Π½ΡƒΡŽ Ρ‚Ρ€ΠΎΠΏΠΈΠ½ΠΊΡƒ ΠΊ остаткам Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΠΎΡ‡Π΅ΠΌΡƒ «остаткам»? Π—Π°Ρ‡Π°ΡΡ‚ΡƒΡŽ Π²Π²ΠΈΠ΄Ρƒ отсутствия Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ памяти приходится ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎ (Π° ΠΈΠ½ΠΎΠ³Π΄Π° ΠΈ рСкурсивно). НадСюсь, Π²Ρ‹ΡˆΠ΅ΠΈΠ·Π»ΠΎΠΆΠ΅Π½Π½ΠΎΠ΅ ΡƒΠ±Π΅Π΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Π΄ΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ написаниС ΠΏΡ€ΠΈΠ²Ρ‹Ρ‡Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° машинС ΠŸΠΎΡΡ‚Π° β€” нСплохая Ρ€Π°Π·ΠΌΠΈΠ½ΠΊΠ° для ΠΌΠΎΠ·Π³ΠΎΠ² ΠΈ вСсьма ΡƒΠ²Π»Π΅ΠΊΠ°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ занятиС.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€

Рассмотрим ΠΎΠ΄Π½Ρƒ ΠΈΠ· ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΡ… Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΉ умноТСния Π΄Π²ΡƒΡ… Π½Π°Ρ‚ΡƒΡ€Π°Π»ΡŒΠ½Ρ‹Ρ… чисСл. Числа n ΠΈ m Π·Π°ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ΡΡ Π½Π° Π»Π΅Π½Ρ‚Π΅ Π² Π΅Π΄ΠΈΠ½ΠΈΡ‡Π½ΠΎΠΉ систСмС счислСния, Ρ€Π°Π·Π΄Π΅Π»ΡΡŽΡ‚ΡΡ ΠΎΠ΄Π½ΠΎΠΉ пустой ячСйкой. Π’Ρ…ΠΎΠ΄/Π²Ρ‹Ρ…ΠΎΠ΄ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Ρ‚Π°ΠΊΠΈΠΌ (ΠΎΡ‚ΠΌΠ΅Ρ‡Π΅Π½ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠΈ):

ИдСя Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° β€” ΠΊΡ€Π°Ρ‚ΠΊΠΎΠ΅ слоТСниС. Π’ ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΏΡ€ΠΎΡ…ΠΎΠ΄Π΅ Ρ†ΠΈΠΊΠ»Π° машина «откусываСт» ΠΎΠ΄ΠΈΠ½ Π±ΠΈΡ‚ ΠΎΡ‚ Π»Π΅Π²ΠΎΠ³ΠΎ мноТитСля ΠΈ Β«ΠΊΠΎΠΏΠΈΡ€ΡƒΠ΅Ρ‚Β» самый ΠΏΡ€Π°Π²Ρ‹ΠΉ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΠΉΡΡ Π±Π»ΠΎΠΊ (спСрва это Π²Ρ‚ΠΎΡ€ΠΎΠΉ ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒ, Π·Π°Ρ‚Π΅ΠΌ β€” Π΅Π³ΠΎ послСдняя копия). Когда Π»Π΅Π²Ρ‹ΠΉ ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒ «закончится», Π½Π° Π»Π΅Π½Ρ‚Π΅ остаСтся n Π±Π»ΠΎΠΊΠΎΠ² ΠΏΠΎ m Π΅Π΄ΠΈΠ½ΠΈΡ†. Π˜Ρ… слияниС Π΄Π°Π΅Ρ‚ искомоС число n*m.

ΠŸΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ½ΠΎ Π² ΡƒΠΌΠ΅, Π½Π° листочкС, Π»ΠΈΠ±ΠΎ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ этой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹.

Π­Ρ‚ΠΎ самая короткая извСстная ΠΌΠ½Π΅ рСализация умноТСния. Однако, ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎ Π΅Π΅ ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠΆΠ°Ρ‚ΡŒ Π΅Ρ‰Π΅ сильнСС, Ссли ΠΏΡ€ΠΈΠ΄ΡƒΠΌΠ°Ρ‚ΡŒ, ΠΊΠ°ΠΊ экономно ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½ΠΈΡ‚ΡŒ процСссы создания ΠΊΠΎΠΏΠΈΠΉ ΠΈ ΠΈΡ… слияния Π² Π΅Π΄ΠΈΠ½Ρ‹ΠΉ массив.

P. S. Β«Π‘ΠΎΠ»ΡŒΡˆΠΎΠΉ Ρ‡Π΅Ρ‚Π²Π΅Ρ€ΠΊΠΎΠΉΒ» Π½Π°Π·Ρ‹Π²Π°ΡŽ ΠΌΠ°ΡˆΠΈΠ½Ρƒ Π’ΡŒΡŽΡ€ΠΈΠ³Π°, ΠŸΠΎΡΡ‚Π°, систСму ΠœΠ°Ρ€ΠΊΠΎΠ²Π° ΠΈ Brainfuck β€” самыС ΠΈΠ·ΡƒΡ‡Π°Π΅ΠΌΡ‹Π΅ Ρ‚ΡŒΡŽΡ€ΠΈΠ½Π³ΠΎΠ²Ρ‹Π΅ трясины.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7 АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…

ΠŸΡ€ΠΎΡΠΌΠΎΡ‚Ρ€ содСрТимого Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Π°
Β«ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7 АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…Β»

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7

АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…

ЦСль Ρ€Π°Π±ΠΎΡ‚Ρ‹: знакомство с основами Ρ‚Π΅ΠΎΡ€ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ Π½Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ алгоритмичСской машиной ΠŸΠΎΡΡ‚Π°.

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ обСспСчСниС: ΠΈΠΌΠΈΡ‚Π°Ρ‚ΠΎΡ€ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°

БистСма ΠΊΠΎΠΌΠ°Π½Π΄ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°: (Π²Π΅Π·Π΄Π΅ Π±ΡƒΠΊΠ²Π° n ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ Π½ΠΎΠΌΠ΅Ρ€ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΈΠ· Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния (Π½.с.) Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ (ΠΊ.с.):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π—Π°Π΄Π°Π½ΠΈΠ΅ 2
1. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚Π΅ Π½Π° машинС ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ:

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

2. ΠšΠ°ΠΊΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ Ρ€Π΅ΡˆΠ°Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ ΠΏΠΎ этой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅?

3. Π§Ρ‚ΠΎ ΠΏΡ€ΠΎΠΈΠ·ΠΎΠΉΠ΄Ρ‘Ρ‚, Ссли Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ Π²ΠΈΠ΄?

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… Π·Π°Π΄Π°Ρ‡Π°Ρ… считаСтся, Ρ‡Ρ‚ΠΎ n располоТСнных подряд ΠΌΠ΅Ρ‚ΠΎΠΊ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ число n (нСпозиционная систСма счислСния с основаниСм 1).

Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΈΠ· Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅:

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7 АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…

ΠŸΡ€ΠΎΡΠΌΠΎΡ‚Ρ€ содСрТимого Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Π°
Β«ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7 АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…Β»

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 7

АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…

ЦСль Ρ€Π°Π±ΠΎΡ‚Ρ‹: знакомство с основами Ρ‚Π΅ΠΎΡ€ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ Π½Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ алгоритмичСской машиной ΠŸΠΎΡΡ‚Π°.

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ обСспСчСниС: ΠΈΠΌΠΈΡ‚Π°Ρ‚ΠΎΡ€ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°

БистСма ΠΊΠΎΠΌΠ°Π½Π΄ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°: (Π²Π΅Π·Π΄Π΅ Π±ΡƒΠΊΠ²Π° n ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ Π½ΠΎΠΌΠ΅Ρ€ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΈΠ· Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния (Π½.с.) Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ (ΠΊ.с.):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π—Π°Π΄Π°Π½ΠΈΠ΅ 2
1. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚Π΅ Π½Π° машинС ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ:

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

2. ΠšΠ°ΠΊΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ Ρ€Π΅ΡˆΠ°Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ ΠΏΠΎ этой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅?

3. Π§Ρ‚ΠΎ ΠΏΡ€ΠΎΠΈΠ·ΠΎΠΉΠ΄Ρ‘Ρ‚, Ссли Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ Π²ΠΈΠ΄?

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… Π·Π°Π΄Π°Ρ‡Π°Ρ… считаСтся, Ρ‡Ρ‚ΠΎ n располоТСнных подряд ΠΌΠ΅Ρ‚ΠΎΠΊ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ число n (нСпозиционная систСма счислСния с основаниСм 1).

Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΈΠ· Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅:

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒΠ’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒΠ’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’ качСствС ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°, Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‰Π΅Π³ΠΎ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΡƒ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ, рассмотрим ΠΌΠ°ΡˆΠΈΠ½Ρƒ Π­. ΠŸΠΎΡΡ‚Π°. Алгоритм, ΠΏΠΎ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌΡƒ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ машина ΠŸΠΎΡΡ‚Π°, Π±ΡƒΠ΄Π΅ΠΌ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΎΠΉ.

Договоримся ΠΎ Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ: ΠΏΠΎΠ΄ словом Β«ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ°Β» ΠΌΡ‹ всСгда Π±ΡƒΠ΄Π΅ΠΌ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, записанный ΠΏΠΎ строгим ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌ языка ΠΊΠΎΠΌΠ°Π½Π΄ исполнитСля β€” Π½Π° языкС программирования для Π΄Π°Π½Π½ΠΎΠ³ΠΎ исполнитСля.

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

ОпишСм Π°Ρ€Ρ…ΠΈΡ‚Π΅ΠΊΡ‚ΡƒΡ€Ρƒ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° (рис. 2.3).

Π˜ΠΌΠ΅Π΅Ρ‚ΡΡ бСсконСчная информационная Π»Π΅Π½Ρ‚Π°, раздСлСнная Π½Π° ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ β€” ΠΊΠ»Π΅Ρ‚ΠΊΠΈ. Π’ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π»ΠΈΠ±ΠΎ ΡΡ‚ΠΎΡΡ‚ΡŒ ΠΌΠ΅Ρ‚ΠΊΠ° (Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π·Π½Π°ΠΊ), Π»ΠΈΠ±ΠΎ ΠΎΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ (пусто).

Π’Π΄ΠΎΠ»ΡŒ Π»Π΅Π½Ρ‚Ρ‹ двиТСтся ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠ° β€” ΡΡ‡ΠΈΡ‚Ρ‹Π²Π°ΡŽΡ‰Π΅Π΅ устройство. На рисункС 2.3 ΠΎΠ½Π° ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½Π° стрСлкой.

ΠšΠ°Ρ€Π΅Ρ‚ΠΊΠ° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠ΅Ρ€Π΅Π΄Π²ΠΈΠ³Π°Ρ‚ΡŒΡΡ шагами: ΠΎΠ΄ΠΈΠ½ шаг β€” смСщСниС Π½Π° ΠΎΠ΄Π½Ρƒ ΠΊΠ»Π΅Ρ‚ΠΊΡƒ Π²ΠΏΡ€Π°Π²ΠΎ ΠΈΠ»ΠΈ Π²Π»Π΅Π²ΠΎ. ΠšΠ»Π΅Ρ‚ΠΊΡƒ, ΠΏΠΎΠ΄ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ установлСна ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠ°, Π±ΡƒΠ΄Π΅ΠΌ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ.

ΠšΠ°Ρ€Π΅Ρ‚ΠΊΠ° являСтся Π΅Ρ‰Π΅ ΠΈ процСссором ΠΌΠ°ΡˆΠΈΠ½Ρ‹.

Π‘ Π΅Π΅ ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ машина ΠΌΠΎΠΆΠ΅Ρ‚:

НазначСниС ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° β€” ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚ΡŒ прСобразования Π½Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Π΅. Π˜ΡΡ…ΠΎΠ΄Π½ΠΎΠ΅ состояниС Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ ΠΊΠ°ΠΊ исходныС Π΄Π°Π½Π½Ρ‹Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ, ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ состояниС Π»Π΅Π½Ρ‚Ρ‹ β€” ΠΊΠ°ΠΊ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ. ΠšΡ€ΠΎΠΌΠ΅ Ρ‚ΠΎΠ³ΠΎ, Π² исходныС Π΄Π°Π½Π½Ρ‹Π΅ Π²Ρ…ΠΎΠ΄ΠΈΡ‚ информация ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠΌ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠΈ ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠΈ.

Π’Π΅ΠΏΠ΅Ρ€ΡŒ рассмотрим систСму ΠΊΠΎΠΌΠ°Π½Π΄ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° (Ρ‚Π°Π±Π». 2.1). Π—Π°ΠΏΠΈΡΡŒ всякой ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹ начинаСтся с Π΅Π΅ порядкового Π½ΠΎΠΌΠ΅Ρ€Π° Π² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅ β€” n. Π—Π°Ρ‚Π΅ΠΌ слСдуСт ΠΊΠΎΠ΄ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ ΠΈ послС Π½Π΅Π³ΠΎ β€” Π½ΠΎΠΌΠ΅Ρ€ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ выполняСмой ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ β€” m.

Рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ Π½Π° машинС ΠŸΠΎΡΡ‚Π°. Π˜ΡΡ…ΠΎΠ΄Π½ΠΎΠ΅ состояниС ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π½Π° рис. 2.3. Машина Π΄ΠΎΠ»ΠΆΠ½Π° ΡΡ‚Π΅Ρ€Π΅Ρ‚ΡŒ Π·Π½Π°ΠΊ Π² Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ ΠΈ ΠΏΡ€ΠΈΡΠΎΠ΅Π΄ΠΈΠ½ΠΈΡ‚ΡŒ Π΅Π³ΠΎ слСва ΠΊ Π³Ρ€ΡƒΠΏΠΏΠ΅ Π·Π½Π°ΠΊΠΎΠ², располоТСнных справа ΠΎΡ‚ ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠΈ. ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π° Π² Ρ‚Π°Π±Π». 2.2.

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’ процСссС выполнСния ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡ€Π°Ρ‚Π½ΠΎ повторяСтся Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΊΠΎΠΌΠ°Π½Π΄ с Π½ΠΎΠΌΠ΅Ρ€Π°ΠΌΠΈ 2 ΠΈ 3. Вакая ситуация называСтся Ρ†ΠΈΠΊΠ»ΠΎΠΌ. Напомним, Ρ‡Ρ‚ΠΎ Ρ†ΠΈΠΊΠ» относится ΠΊ числу основных алгоритмичСских структур вмСстС со слСдованиСм ΠΈ Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΠ΅ΠΌ.

А Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ Π½Π°ΡƒΡ‡ΠΈΠΌ ΠΌΠ°ΡˆΠΈΠ½Ρƒ ΠŸΠΎΡΡ‚Π° ΠΈΠ³Ρ€Π°Ρ‚ΡŒ Π² ΠΈΠ½Ρ‚Π΅Π»Π»Π΅ΠΊΡ‚ΡƒΠ°Π»ΡŒΠ½ΡƒΡŽ ΠΈΠ³Ρ€Ρƒ, которая называСтся Β«Π˜Π³Ρ€Π° Π‘Π°ΡˆΠ΅Β».

ОпишСм ΠΏΡ€Π°Π²ΠΈΠ»Π° ΠΈΠ³Ρ€Ρ‹.

Π˜Π³Ρ€Π°ΡŽΡ‚ Π΄Π²ΠΎΠ΅. ΠŸΠ΅Ρ€Π΅Π΄ Π½ΠΈΠΌΠΈ 21 (ΠΈΠ»ΠΈ 16, ΠΈΠ»ΠΈ 11 ΠΈ Ρ‚. Π΄.) Ρ„ΠΈΡˆΠΊΠ°. Π˜Π³Ρ€ΠΎΠΊΠΈ Π±Π΅Ρ€ΡƒΡ‚ Ρ„ΠΈΡˆΠΊΠΈ ΠΏΠΎ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ. Π—Π° ΠΎΠ΄ΠΈΠ½ Ρ…ΠΎΠ΄ ΠΌΠΎΠΆΠ½ΠΎ Π²Π·ΡΡ‚ΡŒ ΠΎΡ‚ 1 Π΄ΠΎ 4 Ρ„ΠΈΡˆΠ΅ΠΊ. ΠŸΡ€ΠΎΠΈΠ³Ρ€Ρ‹Π²Π°Π΅Ρ‚ Ρ‚ΠΎΡ‚, ΠΊΡ‚ΠΎ Π·Π°Π±ΠΈΡ€Π°Π΅Ρ‚ послСднюю Ρ„ΠΈΡˆΠΊΡƒ.

Π˜ΠΌΠ΅Π΅Ρ‚ΡΡ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹ΡˆΠ½Π°Ρ Ρ‚Π°ΠΊΡ‚ΠΈΠΊΠ° для ΠΈΠ³Ρ€ΠΎΠΊΠ°, Π±Π΅Ρ€ΡƒΡ‰Π΅Π³ΠΎ Ρ„ΠΈΡˆΠΊΠΈ Π²Ρ‚ΠΎΡ€Ρ‹ΠΌ. Она Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π±Ρ€Π°Ρ‚ΡŒ Ρ‚Π°ΠΊΠΎΠ΅ количСство Ρ„ΠΈΡˆΠ΅ΠΊ, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ дополняСт число Ρ„ΠΈΡˆΠ΅ΠΊ, взятых сопСрником Π½Π° ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅ΠΌ Ρ…ΠΎΠ΄Π΅, Π΄ΠΎ пяти.

Роль Ρ„ΠΈΡˆΠ΅ΠΊ Π½Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° Π±ΡƒΠ΄ΡƒΡ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒ ΠΌΠ΅Ρ‚ΠΊΠΈ (Π·Π½Π°ΠΊΠΈ). Машина ΠΈΠ³Ρ€Π°Π΅Ρ‚ с Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΠΎΠΌ. Π§Π΅Π»ΠΎΠ²Π΅ΠΊΡƒ прСдоставляСтся Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΡΡ‚ΠΈΡ€Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΊΠΈ (Π±Ρ€Π°Ρ‚ΡŒ Ρ„ΠΈΡˆΠΊΠΈ) ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ. Машина Π±ΡƒΠ΄Π΅Ρ‚ Π²ΡΡ‚ΡƒΠΏΠ°Ρ‚ΡŒ Π² ΠΈΠ³Ρ€Ρƒ Π²Ρ‚ΠΎΡ€ΠΎΠΉ.

Π˜ΡΡ…ΠΎΠ΄Π½Π°Ρ обстановка: Π½Π° Π»Π΅Π½Ρ‚Π΅ массив ΠΈΠ· 21 ΠΊΠ»Π΅Ρ‚ΠΊΠΈ содСрТит ΠΌΠ΅Ρ‚ΠΊΠΈ. ΠšΠ°Ρ€Π΅Ρ‚ΠΊΠ° установлСна Π½Π° ΠΊΡ€Π°ΠΉΠ½Π΅ΠΉ слСва ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ этого массива. Π‘Ρ‚ΠΈΡ€Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΊΠΈ ΠΌΠΎΠΆΠ½ΠΎ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ подряд. Π’Ρ‹ΠΈΠ³Ρ€Ρ‹ΡˆΠ½Ρ‹ΠΌ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠΌ Π΄ΠΎΠ»ΠΆΠ½Π° Π±Ρ‹Ρ‚ΡŒ ΠΎΠ΄Π½Π° ΠΎΡΡ‚Π°Π²ΡˆΠ°ΡΡΡ ΠΌΠ΅Ρ‚ΠΊΠ° ΠΏΠ΅Ρ€Π΅Π΄ ΠΎΡ‡Π΅Ρ€Π΅Π΄Π½Ρ‹ΠΌ Ρ…ΠΎΠ΄ΠΎΠΌ Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΠ°.

Π•Ρ‰Π΅ Ρ€Π°Π· Π½Π°ΠΏΠΎΠΌΠ½ΠΈΠΌ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹ΡˆΠ½ΠΎΠΉ Ρ‚Π°ΠΊΡ‚ΠΈΠΊΠΈ: ΡΡ‚ΠΈΡ€Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΌΠ΅Ρ‚ΠΎΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π² суммС с ΠΌΠ΅Ρ‚ΠΊΠ°ΠΌΠΈ, стСртыми ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΈΠΊΠΎΠΌ Π·Π° ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰ΠΈΠΉ Ρ…ΠΎΠ΄, ΠΈΡ… Π±Ρ‹Π»ΠΎ ΠΏΡΡ‚ΡŒ.

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° управлСния машиной ΠŸΠΎΡΡ‚Π° Π² ΠΈΠ³Ρ€Π΅ Π‘Π°ΡˆΠ΅ ΠΏΡ€ΠΎΡ‚ΠΈΠ² Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΠ° ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π° Π² Ρ‚Π°Π±Π». 2.3.

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

ДСйствуя ΠΏΠΎ Π΄Π°Π½Π½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅ ΠΈ начиная ΡΡ‚ΠΈΡ€Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΊΠΈ Π²Ρ‚ΠΎΡ€ΠΎΠΉ послС Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΠ°, машина всСгда Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Π²Π°Ρ‚ΡŒ, Ссли ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎ Π·Π°Π΄Π°Π½ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ число ΠΌΠ΅Ρ‚ΠΎΠΊ, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ Ρ€Π°Π²Π½ΠΎ 5n + 1, Π³Π΄Π΅ n β€” любоС Π½Π°Ρ‚ΡƒΡ€Π°Π»ΡŒΠ½ΠΎΠ΅ число. Π’ ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΎΠΌ случаС машина ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€ΠΎΠΈΠ³Ρ€Π°Ρ‚ΡŒ.

ПодвСдСм ΠΈΡ‚ΠΎΠ³.

АвтоматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Π°, Ссли:

1) информация прСдставлСна Π² Ρ„ΠΎΡ€ΠΌΠ°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π½ΠΎΠΌ Π²ΠΈΠ΄Π΅ β€” Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠΌ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π·Π½Π°ΠΊΠΎΠ²ΠΎΠΉ систСмы;
2) Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ ΠΈΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ, ΠΎΠ±Π»Π°Π΄Π°ΡŽΡ‰ΠΈΠΉ ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠΉ систСмой ΠΊΠΎΠΌΠ°Π½Π΄, достаточной для построСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ класса Π·Π°Π΄Π°Ρ‡ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ;
3) Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ΠΎ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ исполнитСля. Машина ΠŸΠΎΡΡ‚Π° β€” ΠΏΡ€ΠΈΠΌΠ΅Ρ€ автоматичСского исполнитСля ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ с ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½Π½Ρ‹ΠΌΠΈ возмоТностями. ΠšΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€ удовлСтворяСт всСм Π²Ρ‹ΡˆΠ΅ΠΏΠ΅Ρ€Π΅Ρ‡ΠΈΡΠ»Π΅Π½Π½Ρ‹ΠΌ свойствам. Он являСтся ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½Ρ‹ΠΌ автоматичСским исполнитСлСм ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ.

БистСма основных понятий

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Вопросы ΠΈ задания

1. На ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° располоТСн массив ΠΈΠ· N ΠΌΠ΅Ρ‚ΠΎΠΊ. ΠšΠ°Ρ€Π΅Ρ‚ΠΊΠ° находится ΠΏΠΎΠ΄ ΠΊΡ€Π°ΠΉΠ½Π΅ΠΉ Π»Π΅Π²ΠΎΠΉ ΠΌΠ΅Ρ‚ΠΊΠΎΠΉ. КакоС состояниС установится Π½Π° Π»Π΅Π½Ρ‚Π΅ послС выполнСния ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹?

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

2. На ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Π΅ Π½Π° Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ расстоянии справа ΠΎΡ‚ ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠΈ, стоящСй ΠΏΠΎΠ΄ пустой ΠΊΠ»Π΅Ρ‚ΠΊΠΎΠΉ, находится Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½Ρ‹ΠΉ массив ΠΌΠ΅Ρ‚ΠΎΠΊ. ВрСбуСтся ΠΏΡ€ΠΈΡΠΎΠ΅Π΄Ρ€ΡˆΠΈΡ‚ΡŒ ΠΊ ΠΏΡ€Π°Π²ΠΎΠΌΡƒ ΠΊΠΎΠ½Ρ†Ρƒ массива ΠΎΠ΄Π½Ρƒ ΠΌΠ΅Ρ‚ΠΊΡƒ.

4. На Π»Π΅Π½Ρ‚Π΅ располоТСн массив ΠΈΠ· 2n ΠΌΠ΅Ρ‚ΠΎΠΊ. Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ, ΠΏΠΎ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ машина Ρ€Π°Π·Π΄Π²ΠΈΠ½Π΅Ρ‚ Π½Π° расстояниС Π² ΠΎΠ΄Π½Ρƒ ΠΊΠ»Π΅Ρ‚ΠΊΡƒ Π΄Π²Π΅ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρ‹ Π΄Π°Π½Π½ΠΎΠ³ΠΎ массива.

ΠŸΡ€Π°ΠΊΡ‚ΠΈΠΊΡƒΠΌ

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° β„– 2.2 «ΠΠ²Ρ‚оматичСская ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Π΄Π°Π½Π½Ρ‹Ρ…»

ЦСль Ρ€Π°Π±ΠΎΡ‚Ρ‹: знакомство с основами Ρ‚Π΅ΠΎΡ€ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ Π½Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ алгоритмичСской машиной ΠŸΠΎΡΡ‚Π°.

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠ΅ обСспСчСниС: ΠΈΠΌΠΈΡ‚Π°Ρ‚ΠΎΡ€ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°, (ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠ°Ρ‡Π°Ρ‚ΡŒ ΠΎΡ‚ΡΡŽΠ΄Π°).

БистСма ΠΊΠΎΠΌΠ°Π½Π΄ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π°: (Π²Π΅Π·Π΄Π΅ Π±ΡƒΠΊΠ²Π° n ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ Π½ΠΎΠΌΠ΅Ρ€ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π—Π°Π΄Π°Π½ΠΈΠ΅ 1

Π‘ΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΈΠ· Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния (Π½.с.) Π² ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ (ΠΊ.Π΅.):

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π—Π°Π΄Π°Π½ΠΈΠ΅ 2

1. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ:

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

2. ΠšΠ°ΠΊΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ Ρ€Π΅ΡˆΠ°Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒ ΠΏΠΎ этой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅?

3. Π§Ρ‚ΠΎ ΠΏΡ€ΠΎΠΈΠ·ΠΎΠΉΠ΄Π΅Ρ‚, Ссли Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Ρ‹ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ Π²ΠΈΠ΄?

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π’ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… Π·Π°Π΄Π°Ρ‡Π°Ρ… считаСтся, Ρ‡Ρ‚ΠΎ n располоТСнных подряд ΠΌΠ΅Ρ‚ΠΎΠΊ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ число n (нСпозиционная систСма счислСния с основаниСм 1).

Π—Π°Π΄Π°Π½ΠΈΠ΅ 3

ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ для ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ слоТСния Π΄Π²ΡƒΡ… чисСл, записанных Π½Π° Π»Π΅Π½Ρ‚Π΅ ΠΈ располоТСнных Ρ‡Π΅Ρ€Π΅Π· ΠΎΠ΄Π½Ρƒ ΠΏΡƒΡΡ‚ΡƒΡŽ ΠΊΠ»Π΅Ρ‚ΠΊΡƒ Π΄Ρ€ΡƒΠ³ ΠΎΡ‚ Π΄Ρ€ΡƒΠ³Π°. ΠΠ°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠΈ β€” ΠΏΠΎΠ΄ пустой ΠΊΠ»Π΅Ρ‚ΠΊΠΎΠΉ, ΠΎΡ‚Π΄Π΅Π»ΡΡŽΡ‰Π΅ΠΉ числа.

Π—Π°Π΄Π°Π½ΠΈΠ΅ 4

ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ для ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ вычитания Π΄Π²ΡƒΡ… чисСл, Ρ€Π°Π·Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… ΠΎΠ΄Π½ΠΎΠΉ пустой ΠΊΠ»Π΅Ρ‚ΠΊΠΎΠΉ. УмСньшаСмоС Π½Π΅ мСньшС Π²Ρ‹Ρ‡ΠΈΡ‚Π°Π΅ΠΌΠΎΠ³ΠΎ. ΠΠ°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠΈ β€” ΠΏΠΎΠ΄ пустой ΠΊΠ»Π΅Ρ‚ΠΊΠΎΠΉ, ΠΎΡ‚Π΄Π΅Π»ΡΡŽΡ‰Π΅ΠΉ ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅ΠΌΠΎΠ΅ ΠΎΡ‚ Π²Ρ‹Ρ‡ΠΈΡ‚Π°Π΅ΠΌΠΎΠ³ΠΎ.

Π£ΠΊΠ°Π·Π°Π½ΠΈΠ΅. Π‘Ρ‚ΠΈΡ€Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΊΠΈ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΉ Ρƒ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ числа, ΠΏΠΎΠΊΠ° Ρƒ Π²Ρ‹Ρ‡ΠΈΡ‚Π°Π΅ΠΌΠΎΠ³ΠΎ Π½Π΅ кончатся всС ΠΌΠ΅Ρ‚ΠΊΠΈ.

Π—Π°Π΄Π°Π½ΠΈΠ΅ 5

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ вычитания, ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ получится, Ссли:

Π°) ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅ΠΌΠΎΠ΅ Ρ€Π°Π²Π½ΠΎ Π²Ρ‹Ρ‡ΠΈΡ‚Π°Π΅ΠΌΠΎΠΌΡƒ;
Π±) ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅ΠΌΠΎΠ΅ мСньшС Π²Ρ‹Ρ‡ΠΈΡ‚Π°Π΅ΠΌΠΎΠ³ΠΎ.

Π—Π°Π΄Π°Π½ΠΈΠ΅ 6

ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ для ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ дСлСния числа, записанного ΠΌΠ΅Ρ‚ΠΊΠ°ΠΌΠΈ, Π½Π° 2. Π˜ΡΡ…ΠΎΠ΄Π½ΠΎΠ΅ число Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π΄Π΅Π»ΠΈΡ‚ΡŒΡΡ Π½Π° 2 Π±Π΅Π· остатка.

Π£ΠΊΠ°Π·Π°Π½ΠΈΠ΅. Π‘Ρ‚Π΅Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄ΡƒΡŽ Π²Ρ‚ΠΎΡ€ΡƒΡŽ ΠΌΠ΅Ρ‚ΠΊΡƒ; ΡƒΠΏΠ»ΠΎΡ‚Π½ΠΈΡ‚ΡŒ ΠΎΡΡ‚Π°Π²ΡˆΠΈΠ΅ΡΡ ΠΌΠ΅Ρ‚ΠΊΠΈ.

Π—Π°Π΄Π°Π½ΠΈΠ΅ 7

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ дСлСния числа Π½Π° 2: Π°) ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ получится для числа 2; Π±) ΠΌΠΎΠ΄ΠΈΡ„ΠΈΡ†ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ с ΡƒΡ‡Π΅Ρ‚ΠΎΠΌ числа 2.

Π£ΠΊΠ°Π·Π°Π½ΠΈΠ΅. Π‘ΠΏΡ€Π°Π²Π° ΠΎΡ‚ пустой ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΌΠ΅Ρ‚ΠΊΡƒ, Π° слСва ΡΡ‚Π΅Ρ€Π΅Ρ‚ΡŒ Π΄Π²Π΅ ΠΌΠ΅Ρ‚ΠΊΠΈ. Π’Π°ΠΊ ΠΏΠΎΡΡ‚ΡƒΠΏΠ°Ρ‚ΡŒ Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° слСва ΠΎΡΡ‚Π°ΡŽΡ‚ΡΡ ΠΌΠ΅Ρ‚ΠΊΠΈ.

Π—Π°Π΄Π°Π½ΠΈΠ΅ 8

На ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° Π½Π° расстоянии Π² Π³Π° ΠΊΠ»Π΅Ρ‚ΠΎΠΊ Π΄Ρ€ΡƒΠ³ ΠΎΡ‚ Π΄Ρ€ΡƒΠ³Π° располоТСны Π΄Π²Π΅ ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Π½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΊΠ°ΠΌΠΈ ΠΊΠ»Π΅Ρ‚ΠΊΠΈ. ΠΠ°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΊΠ°Ρ€Π΅Ρ‚ΠΊΠΈ β€” ΠΏΠΎΠ΄ Π»Π΅Π²ΠΎΠΉ ΠΈΠ· ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Π½Ρ‹Ρ… ΠΊΠ»Π΅Ρ‚ΠΎΠΊ. ΠšΠ°ΠΊΡƒΡŽ Ρ€Π°Π±ΠΎΡ‚Ρƒ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ Машина ΠŸΠΎΡΡ‚Π° ΠΏΠΎ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅?

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ. Π€ΠΎΡ‚ΠΎ Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π½Π° машинС поста ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ

Π—Π°Π΄Π°Π½ΠΈΠ΅ 9

ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ для ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ умноТСния Π½Π° 2 числа, записанного ΠΌΠ΅Ρ‚ΠΊΠ°ΠΌΠΈ Π½Π° Π»Π΅Π½Ρ‚Π΅.

Π£ΠΊΠ°Π·Π°Π½ΠΈΠ΅. Π§Π΅Ρ€Π΅Π· ΠΎΠ΄Π½Ρƒ ΠΏΡƒΡΡ‚ΡƒΡŽ ΠΊΠ»Π΅Ρ‚ΠΊΡƒ ΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π΄Π²Π΅ ΠΌΠ΅Ρ‚ΠΊΠΈ, Π° Π² исходном числС ΡΡ‚Π΅Ρ€Π΅Ρ‚ΡŒ ΠΎΠ΄Π½Ρƒ. Π’Π°ΠΊ ΠΏΠΎΡΡ‚ΡƒΠΏΠ°Ρ‚ΡŒ, ΠΏΠΎΠΊΠ° Π² исходном числС ΠΎΡΡ‚Π°ΡŽΡ‚ΡΡ ΠΌΠ΅Ρ‚ΠΊΠΈ.

Π—Π°Π΄Π°Π½ΠΈΠ΅ 10*

ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ для ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ, ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡΡŽΡ‰ΡƒΡŽ, дСлится Π»ΠΈ записанноС ΠΌΠ΅Ρ‚ΠΊΠ°ΠΌΠΈ число Π½Π° 5.

Π—Π°Π΄Π°Π½ΠΈΠ΅ 11*

Π—Π°Π΄Π°Π½ΠΈΠ΅ 12*

На ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Π»Π΅Π½Ρ‚Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠŸΠΎΡΡ‚Π° располоТСны Π΄Π²Π° массива ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Π½Ρ‹Ρ… ΠΊΠ»Π΅Ρ‚ΠΎΠΊ. ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ стирания ΠΌΠ΅Ρ‚ΠΎΠΊ, располоТСнных Π² большСм массивС.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΉ

Π’Π°Ρˆ адрСс email Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π½. ΠžΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ поля ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Ρ‹ *