AOP_Tom1 (1021736), страница 146
Текст из файла (страница 146)
Из (а) и того, что О < У < и, получаем Х .!. У и Х/У > хв+!/уве!. Поэтому, если Л/У ~ хвез/увез, то по определению Л/У > хв+з/ув+з. Отсюда щгедует, что Ху,+, - У .,+, Х 1 ув+! 1 ув+! У ув+! 1 + 1 у!,.!.! + У вЂ” > п Уув+з ув+!уь вг Ууве!увез Ууь+!увэз Уув.н Исторические замечания. К Гарос (С Нагов) предложил более сложное правило построения таких последовательностей в работе з. г(е !'Есо!е Ро!увесбтоое 4, 11 (1802), 364 — 368; его метод правилен, но доказательство несовершенно.
Несколькими годами позже геолог Джон Фарой (ЗоЬп гагеу) независимо предположил, что хв/ув всегда равно (хв ! + ха+!)/(ув — ! ч-уве!) (РЬ!!ов. Мабазп!е апг! зоигпа! 47 (1816), 385-386), доказательство вскоре было предоставлено О Коши (А. СавсЬу) (Вой. Яос(ФМ РЛ(!ота(Абдие бе Рапэ (3) 3 (1816), 133 — 135), который двл этому ряду имя Фарея О других интересных свойствах данных рядов говорится в работе С. Н Нагбу, Е, М %г)ЕЫ, Ал Гпггос(осйоп го (Ле ТЛеогу оу )Чошбегэ, СЬарсег 3.
20. « ЗАДАЧА О СИГНАЛАХ СВЕТОФОРА 1Н ВБТХЕ ЕОО 1(4:4) 2ВБ12Е ЕОО 2(4:4) ВЕЬАТ БТ) 1Р ВЕСА 6 ВЕСА 2 БАР «-1 БАН «+2 НОР 1Н )ИР « РЬАБН БТ) 2Р ЕНТ2 8 1Н ЬВА 49991 )ИР ВЕЬАТ ВЕСХ 0.1 ЬВА 49996 )ИР ВЕЬАТ ТИСХ 0.1 ВЕС2 1 )22 1Р ЬВА =49993 )ИР 1В ЬВА =399992 ЗНР ВЕЬАТ 2Н ЭНР ВАХТ )НОЧ « ТАТР ТИСХ ВБТХЕ ЕНТ1 2ВБ12Е ЗНР РЬАБН ЬВХ НАИВЕН ЬВА 799995 ЛИР ВЕЬАТ ЬВХ АСНЕЕИ ЬВА 799996= ЗНР ВЕЬАТ ТИСХ 1 ЕНТ1 2 )ИР РЬАБН 101 ААНВЕН )ОЧ «+1 ЬВА 499994 Л(Р ВЕЬАТ ВЕО1И ЬВХ ВСЙЕЕИ ЬВА 1799994 Л(Р ВЕЬАТ Л(Р НА1Т 4 5 7 8 9 2 3 4 1 2 4 5 4 5 6 5 6 1 2 8 2 3 5 2 3 4 1 2 8 1 3 4 6 2 3 4 Размер байта.
Двойной размер байта. Если в гА содержится и, зта подпрограмма ожидает ровно шах(п, 7) и времени, не считая времени на переход к подпрограмме Это подпрограмма мигания соответствующего сигнала СТОЙТЕ. Выключение сигнала. СТОЙТЕ. Повторить восемь рвз. Вернуться к началу цикла. Установить желтый через 2и после выхода. Зеленый свет на Дель-Мар до момента переключения. На Дель-Мар сигнал СТОЙТЕ. Мигание сигнала на Дель-Мар.
Желтый свет на проспекте. Ожидать 8 с. Зеленый свет на авеню. Ожидать 8 с На Беркли сигнал СТОЙТЕ. Мигание сигнала на Беркли. Желтый свет на авеню Отменить лишнее переключение. Ожидать 5 с. Зеленый свет на проспекте. Ожидать минимум 18 с. Зеленый Желтый Зеленый Желтый АСВЕЕМ АПР САВА ААНВЕВ АПР СВВВ ВСВЕЕМ АПР АСАН ВАНВЕВ ААР ВСВВ ЕМП ВЕСТЕ свет для авеню. свет для авеню. свет на проспекте. свет на проспекте.
22. ь М Н Х ОН Установить в каждой ячейке номер следующего человека в последовательности. (Сейчас гП = О.) (Предполагаем, что М > 2.) Отсчет по кругу. 1Н гП Рз счастливчик. г12 Ря обреченный. г13 = следующий. Сохранить номер казненного.
1.2(4:5) 1 Х,1 0,3 Н 1В Взять человека из круга. Остался один человек; его тожеказнят. Напечатать ответ. Х,1(4:5) Х(18) ОВ Последним остается человек в позиции 15. Общее время выполнения программы без печати результатов составляет (4()У вЂ” 1)(М+ 7 5)+ 16)и Программу можно несколько улучшить, например воспользоваться предложением Д. Инголза (О. 1пЕа!!е) и взять состоящие из трех слов пакеты кода "ПЕС2 1; 12Р МЕХТ; )НР ООТ", где команда ОПТ модифицирует поле МЕХТ таким образом, что удаляет пакет Асимптотически более быстрый метод приведен в упр.
5.1.1-5. РАЗДЕЛ 1.3.3 1. (1 2 4)(3 б 5). 2. а (ч с, с е+ (; Ь еч ф Совершенно очевидно, как это обобщить на случай произвольной перестановки. 3 ( бейте У) 4. (адсу е), 5. 12 (см упр 20). ЗАДАЧА ЕОО ЕЯО ОН10 ЕМТ1 ЗТХ ЗТ1 ПЕС1 31Р ЕМТА ЕМТ2 ип ПЕС2 32Р 002 ЮЗ СНАВ ЗТХ МОИ 1МСА ЗТЗ ЕМТ1 СНРА Л.
СНАМ ЗТХ ОПТ Н1.Т ЕМП ИОСИФА 24 11 ь+М М-1 Х+М"1 Х-1,1 1 ь-2 1 Н"2 Х.1 1 ь-2 Х,1 Х.2 1 1 )У вЂ” 1 )У вЂ” 1 )Ч вЂ” 1 1 Ю вЂ” 1 (М вЂ” 2) ()У вЂ” 1) (М вЂ” 2) ()Ч вЂ” 1) (М вЂ” 2) ()У вЂ” 1) )У вЂ” 1 )т' — 1 !'т' — 1 )У вЂ” 1 )У вЂ” 1 )У вЂ” 1 л( — 1 )У вЂ” 1 )У вЂ” 1 )Ч вЂ” 1 1 1 1 1 6. Общее время увеличится на 4и для каждого пустого ввода, перед которым идет непустое слово "(", и еще на 56 для каждого пустого слова, перед которым идет непустое слово-имя Начальные пробелы и пробелы между циклами не оказывают влияния на время выполнения программм Положение пробелов никак не влияет на время выполнения программы В 7.
Х = 2, К = 29, М = 5, Аг = 7, У = 3, )г = 1 Общее время выполнения оггласно (18) равно 2161и 8. Да В этом глучае нужно использовать обратную перестановку, чтобы х, переходило в х, тогда и только тогда, когда Т[7] = г (Тогда окончательный вид циклической формы будет построен справа налево с помощью таблицы Т ) 9. Нет Например, если вводом является (6), то программа А в качестве вывода даст "(400) (СЕ9) ", а программа  — "(СЕВ) (001)" Эти ответы эквивалентны, но не идентичны, так как циклическая запись не единственна В программе А первым элементом цикла выбирается крайний слева, а в программе  — последний отличный от других при движении справа налево 10. (1) По закону Кирхгофа получаем А = 1+ С вЂ” Р, В = А+ у+ Р— 1, С =  — (Р— Е), Е = Р— Е, С = Е, ге = У, Иг = В (2) Объяснение В = число слов ввода = 16Х вЂ” 1, С = число непустых слов = У, Р = С вЂ” М, Е = Р— М, Р = число сравнений при поиске по таблице имен, Н = Аг, К = М, ггг = Аг, Л ж гг, В = Н вЂ” Ъ; Т = Аг — )г, так как каждое из других имен помечено (3) В итоге получаем (4Р+ 16У+80Х+ 21Аг — 19М+ 9гу — 16)г)и Это несколько лучший результат, чем дает программа А, поскольку, безусловно, Г меньше, чем 160!Х Общее время выполнения в данном случае равно 983и, так как Г = 74 11.
"Отразите" ее Например, обратной к перестановке (ос/)(Ьг!) является (г(5)(/ао) 12. (а) Значение, которое находится в ячейке Е+ тп — 1, во время транспонирования остается на месте, поэтому ее можно исключить из рассмотрения А в остальном, если х = п(г — 1) + (7 — 1) < тп — 1, значение из ячейки Е + х должна перейти в ячейку Е + тх шог! Аг = Е+ (тп(г — 1) + т(у — 1) ) шос! Аг = Е+ т(у — 1) + (г — 1), так как тп щ 1 (по модулю Аг) и 0 < т(у — 1) + (г — 1) ( Аг (Ь) Если в каждой ячейке памяти один бит свободен (например, бит знака), элементы можно "помечать" по мере их перемещения с помощью алгоритма, подобного алгоритму 1 [См М Р Вегпгаи, .)АСМ 5 (1958), 383-384 ] Если для битов пометки нет свободного места, та их можно сохранять во вспомогательной таблице или использовать список элементов, содержащихся во всех не единичных циклах Для каждого делителя с( числа Ж можно по отдельности транспонировать те элементы, которые кратиы г1, так как т взаимно просто с Аг Длина цикла, содержащего х, где бсс)(х, Аг) = г(,---это наилгеньшее целое г > О, такое, что т' щ 1 (по модулю Ж/г!) Для каждого г! нужно найти уг(Аг/гг)/г элементов-представителей, по одному из каждого цикла Это можно сделать с помощью ряда теоретико-множественных методов, но они недостаточно просты для того, чтобы мы могли ими удовлетвориться Эффективный, но довольно сложный алгоритм можно получить, применяя теорию чисел, а также используя небольшую таблицу битовпометок [См Н Вгеллег, САСМ 16 (1973), 692 — 694] И наконец, существует метод, который является аналогом алгоритма Л Он работает медленнее, но зато не требеет дополнительной памяти и любие нужные перестановки выполняет гп ейие [Си Р Р 14ггпг(!еу, Сошр 3 2 (1959), 47-48, Р Е КписЬ, Ргос )Р)Р Солбгезэ (1971), 1, 19 — 27, Е С Саее, Р 1Ч Тигбб, АСМ Тгааэ Маей Бо!)ггаге 3 (1977), 104 — 110, Г Е РюЬ, Я ! Милго, Р Ч РоЫесе, 81СОМР 24 (1995), 266-278] 13.
Покажите по индукции, что в начале шага 32 Х[г] = +7 тогда и толька тогда, когда 7 > т и 7 переходит в г в результате перестановки к Х[г] = — 7 тогда и только тогда, когда 'На месте" (лат ) — Прим иерее з переходит в б в результате перестановки з ~+~. где Й вЂ” наименьшее неотрицательное целое, такое,что кз переводит з вчйсло, которое < т. 14.
Запишем обратную перестановку к заданной е канани олеской циклической форме и уберем скобки, Величина А — Х вЂ” это сумма последовательных элементов, которые бшзьше заданного и находмзсм непосредственно справа от него Например, если исходной является перестановка (1 6 5)(3 7 8 4), то канонической формой обратной перестановки будет (3 4 8 7)(2)(1 5 6). Введем массив 3 4 8 7 2 1 5 6 ° ° Величина А — это количество "точек", т. е. она равна 16.
Число точек под )г-и элементом— это количество минимумов справа налево среди первых /с элементов (в приведенном выше примере под элементом 7 находятся 3 точки, так как в последовательности 3 487 всего 3 минимума справа налево). Значит, среднее равно Н~ + Нз+ . + Нв = (и+ 1)Н вЂ” и. 15. Если первым символом линейного представления является 1, то последним снмвшюм канонического представления является 1. Если первым символом линейного представления является некоторое т > 1, то в каноническом представлении появляется "...1т ...". Поэтому единственным решением является перестановка одного объекта. (Можно считать, что существует также перестановка из пустого множества объектов.
16. 1324, 4231, 3214, 4213, 2143, 3412, 2413, 1243, 3421, 1324,.... 17. (а) Вероятность того, что этим циклом является т-цикл, равна и)/т, деленному на и! Н„, т, е. р = 1/(тН„). Средняя длина цикла равна рз + 2рз + 3рз + . ,(т/тН„) = и/Н (Ь) Поскольку общее число т-циклов равно и!/ги, общее число появлений элементов в т-циклах равно иб Согласно свойству симметрии каждый элемент появляется так же часто, как и любой другой, поэтому 1 появляется в т-циклах ьй/и раз. Следовательно, в эгиом случае рю = 1/и для всех Й и т; среднее равно 2 ", т/и = (и+ 1)/2, 18. См. упр. 22, (е). 19.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
