Задачи по программированию

[https]

Доброго времени суток всем. Была бы благодарна за помощь в решении нижепреведённых задач. 1-ая - по языку C/С++, во второй и третьей язык не важен.

1. (Язык C++) Необходимо вычислить сумму ряда 1/1+1/2+...+1/n. Учитывая, что в C++ вычисления являются не точными,
   порядок суммирования играет важную роль. Например, выражение 1/n + 1/(n-1)+...+1/1 дает более точный результат.
   Требуется найти такой порядок ссумирования, который бы выдавал еще более точный ответ.


2. 
   Имеется последовательность чисел, заданная выражением:
   n –> n / 2 (n четное)
   n –> 3n + 1 (n нечетное)
   Последовательность оканчивается, когда n становится равно 1 (рано или поздно это происходит для всех таких последовательностей)
   Пример:
   3-> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
   
   Задача состоит в том, чтобы найти последовательность, которая имеет наибольшую длину, начинающуюся с числа меньше миллиона (последующие числа за предел миллиона выходить могут).
   -------
   Полным перебором задача, естественно, решается, правильный ответ - 837799, длина 525. Но хотелось бы более эффективного решения.
   


3. 
   Рассмотрим алгоритм быстрой сортировки, у которого в качестве опорного элемента используется центральный элемент массива.
   На какой перестановке из девяти элементов алгоритм будет работать максимально долго?
   

@темы: C++, Алгоритм

Comments

[[revolver]]

вторая задача: решаем задачу в обратном порядке -- идём с 1 и говорим откуда мы могли прийти в неё. запоминаем номер шага, в случае когда уже такое число получали -- выбираем максимум из шагов. тема -- динамическое программирование. можно почитать в интернете.

третья задача: [:||||||:] всё очень просто нужно QSort превратить в квадратичную сортировку, т.е. в такую для которой на каждом шаге разбиение будет проходить так: с одной стороны ровно один элемент, с другой -- остальной массив.Например так: 2 4 6 8 9 7 5 3 1, запустите трассировку -- убедитесь)

[Trotil]

Первая задача.
На самом деле можно задать кучу вопросов
Какой тип данных?
n как-то ограничено?
Можно ли вычислять сумму по группам? То есть иметь много переменных и вычислять сумму по кусочкам?
Нужно ли учитывать, что в памяти компьютера некоторые числа с плавающей точкой будут сохраняться неточными значениями? Можно ли оценивать погрешность с помощью мат. методов, зная формат хранения данных?
Кстати, про формат хранения данных полезно почитать

[[revolver]]

Trotil, ну формат хранения думаю IEEE 754-2008, как у всех нормальных людей

[Trotil]

А про формат хранения предложил почитать топикстартеру, ибо, если осведомлен, то будет ясно, какие числа точно представимы в этом формате, какие - нет. ИМХО, это важно для решения задачи.

А IEEE-754 я читал. Кстати, в 2008 есть изменения по сравнению с предыдущей версией.
Из-за этого у нас на работе кое-какая штука перестала ему удовлетворять

[https]

[revolver]
задача 1: не совсем поняла фразу "запоминаем номер шага, в случае когда уже такое число получали -- выбираем максимум из шагов". Можете пояснить подробнее?

задача 3: Про это я слышала, даже в википедии, кажется, написано. Но нет ли формального обоснования, почему этот случай - наихудший?

Trotil

Какой тип данных?

По-моему из того как написан ряд очевидно, что целые.

n как-то ограничено?

Естесственно; гармонический ряд - расходящийся и суммы в бесконечном пределе у него нет

Можно ли вычислять сумму по группам? То есть иметь много переменных и вычислять сумму по кусочкам?

Ммммм... не знаю, наверно можно

Нужно ли учитывать, что в памяти компьютера некоторые числа с плавающей точкой будут сохраняться неточными значениями

Так кажется именно по-этому получается разница в точности вычисления?

Можно ли оценивать погрешность с помощью мат. методов, зная формат хранения данных?

Почему нет?

Про формат хранения данных не в курсе, в условии ничего не было сказано на эту тему; пусть будет IEEE 754-2008, длинное вещественное (double, как я понимаю).

[Trotil]

Можно ли оценивать погрешность с помощью мат. методов, зная формат хранения данных? Почему нет?

А потому что это будет не явное суммирование. а дополнительные вычисления доп. формулами. С таким же успехом можно взять логарифм и постоянную Эйлера и получить ответ. Поэтому и важно - где граница в применимости таких формул и методов.

Естесственно; гармонический ряд - расходящийся и суммы в бесконечном пределе у него нет

Зато при очень больших n при попытке записать число 1/n в ячейку памяти запишется нуль и таким образом сумма не будет меняться, начиная с некоторых n, если суммировать обычным способом. Тут тоже возникает вопрос, насколько можно преобразовывать выражение, чтобы учитывать этот момент.

Про формат хранения данных не в курсе, в условии ничего не было сказано на эту тему; пусть будет IEEE 754-2008.

Тогда вперёд и с песней. Почитайте про этот формат.
Можете сразу так сказать, что это за число - 0x3f80000 ?

[[revolver]]

https, 3. эм... формальнее некуда. получаем квадратичное время. самое что ни на есть печальное)

2. ну тут как бы ещё раз. вот у нас есть 1. её мы получили на 0 шаге. т.е. p[1] = 0;
дальше. какими путями мы могли получить 1?
мы могли прийти в неё по правилу n –> n / 2 (n четное) или n –> 3n + 1 (n нечетное). т.е. или из двойки или из нуля(плохой случай)
т.е. p[2] = 1 -- означает что за 1 шаг с 2 дойдём до 1.
в 2 могли прийти из 4. p[4] = 2 (1 достижима из 4 за 2 шага)
p[8] = 3..
а самое интересное начинается счас...
потому что 16 достижима как с 5 так и с 32
соответственно
5 достижима из 10
32 из 64
....
и так далее.

Реализация: можно рекурсия можно поиск в ширину в графе.

P.S. сорри за мой французский, у меня час ночи времени

[[revolver]]

Trotil для того чтобы такое сказать нужно сделать cout << 0x3f80000

[Trotil]

[revolver]

Он так интерпретирует как int. Не?

[https]

Trotil

А потому что это будет не явное суммирование. а дополнительные вычисления доп. формулами. С таким же успехом можно взять логарифм и постоянную Эйлера и получить ответ. Поэтому и важно - где граница в применимости таких формул.

Цель - не рассчитать как можно более точное значение, а найти порядок, при котором оно будет достигаться. Т.е. причин не использовать мат. методы для оценки погрешности в случае того или иного порядка я не вижу; но исключительно для оценки значения суммы - нет.

Зато при очень больших n при попытке записать число 1/n в ячейку памяти запишется нуль и таким образом сумма не будет меняться, начиная с некоторых n, если суммировать обычным способом. Тут тоже возникает вопрос, насколько можно преобразовывать выражение, чтобы учитывать этот момент.

Мне кажется, вы придираетесь =) Логично, что n - такие, что 1/n в выбранный тип вещественного помещаются, иначе с ними ничего не сделаешь. Преобразовывать выражение, насколько я понимаю, можно только одним способом - менять порядок суммировния членов.

Тогда вперёд и с песней. Почитайте про этот формат.

М, может вы посоветуете какой конкретно раздел почитать? Подозреваю, что стандарт длинный...

Можете сразу так сказать, что это за число - 0x3f80000

Боюсь, не поняла вашего вопроса. Шестнадцатеричное, целое, влезает в четыре байта, значит int. Или со стороны какой характеристики "что за число"?

[[revolver]]

Trotil, да. значит так:
cout << (double)(0 | 0x3f80000);

[https]

[revolver]
3. Мне кажется, это не слишком очевидно, что оно квадратичное. Это как-то можно доказать или я не понимаю очевидных вещей?

2. Рассматривала такой вариант, но самое интересное - в какой момент остановиться? Если очередное число вышло за предел миллиона, это не значит, что предыдущее является начальным. После начального числа 837799 (правильный ответ) последовательность "улетает" за миллион и долго там колбасится, пока не вернётся обратно и спускается к 1.