Международный научно-образовательный электронный журнал «образование и наука в XXI веке». Выпуск №10 (том 1)



Download 5,9 Mb.
Pdf ko'rish
bet49/98
Sana08.04.2022
Hajmi5,9 Mb.
#538253
TuriСборник
1   ...   45   46   47   48   49   50   51   52   ...   98
Bog'liq
«Образование и наука в XXI веке» 1 JILD

Задача 6.
В языке 'программирования MustDie всего две команды, для краткости 
называемых М и О: Из-за сбоя в компьютере, действие программы не изменится, если из 
нее выкинуть кусок кода MDDM, а также если в любое ее место вставить кусок кода 
DMMDMD или МDМD. Могут ли программы MMDMD и DMMDD работать одинаково?
Решение:
Иначе говоря: существует ли такое равнозначное преобразование кода, которое 
переводит одну программу в другую? Нет, конечно, и вы уже догадались ... инвариант 
только надо придумать. В одном куске 2 команды М 2 команды D, во втором тех и других 
по 3, в третьем - опять по 2. Кажется, ясно: в 
любом 
вставляемом или убираемом 
куске 
команд 
М и D 
поровну. 
Значит, не меняется ... правильно, 
разность 
между числом тех и 
других команд. Она будет нашим инвариантом - и очень хорошо, так как в одной программе 
на одну больше команд М, а в другой на одну больше команд D (значение разности 
поменялось в 1 на -1).
Задача 
7. По кругу стоят 232 елки, на каждой из которых сидит по белке. Если какая то 
белка перепрыгивает с одной елки на соседнюю, то какая то другая перепрыгивает на 
соседнюю елку в обратом направлении. Докажите, что все белки не могут собраться на 
одной елке. 
Решение:
Обратите внимание на прием, который мы здесь применим. (Начинающим такое 
обычно в голову не приходит) Давайте 
занумеруем 
елки по кругу от 1 до 232. Тогда каждой 
белке можно сопоставить 
число 
номер елки, на которой она сидит. И все эти прыжки 
представятся, как 
преобразования набора чисел. 
Обычно одна белка, перепрыгивая в одну 
сторону, уменьшает свой номер на 1, а другая, прыгая в другую сторону, увеличивает на 1. 
Конечно,
сумма номеров 
не меняется. А как еще бывает? Либо одна белка прыгает с l-й елки 
на 232-ю, а другая, наоборот,
с 232-й на l-ю (сумма опять не меняется). Либо одна белка прыгает с l-й елки на 232-ю, а 
другая - где-то еще, увеличивая свой номер на 1 - сумма растет на 232. Последний случай: 
одна белка прыгает с 232-й елки на l-ю, а другая - в другом месте, уменьшая номер на 1. 
Тогда сумма номеров уменьшается на 232. В любом случае 
значение суммы номеров по 


109 
модулю 
232 - неизменно (то есть инвариант). Если бы все белки собрались на одной елке, то 
их номера были бы 232-мя одинаковыми числами, и их сумма на 232 делилась бы. Но тогда и 
исходная сумма номеров делилась бы на 232, а этого не наблюдается (эта сумма от 1 до N - 
равна 232*233/2), ч.т.д.

Download 5,9 Mb.

Do'stlaringiz bilan baham:
1   ...   45   46   47   48   49   50   51   52   ...   98




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish