Задача: пропавшее число
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Задача: пропавшее число - 2010-11-02 01:48:20.123333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Задача на несколько этапов. Этап первый.
Есть набор чисел от 1 до 100, причём каждое число встречается ровно один раз. Из этого набора наугад убирают одно число. Как за один проход и с фиксированным количеством памяти узнать, какое именно число было убрано?
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 09:06:05.320000
|
|
|
Flint_ta
Сообщений: 3720
Оценки: 1120
Присоединился: 2007-01-26 15:49:18.323333
|
Возможно задачу не до конца понял.
1. получить сумму всех чисел от 1 до 100.
2. получить сумму оставшихся чисел (после того как наугад одно убрали)
3. разница сумм в п.1. и п.2 есть число которое убрали.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 09:49:51.670000
|
|
|
disCoverall
Сообщений: 32
Оценки: 0
Присоединился: 2010-10-31 00:43:50.613333
|
int x,y,;
cout << "Введите убираемое число";
cin>>x;
y= x;
cout << "Ваше число";
xDDD)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 13:00:02.420000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Flint_ta
Возможно задачу не до конца понял.
1. получить сумму всех чисел от 1 до 100.
2. получить сумму оставшихся чисел (после того как наугад одно убрали)
3. разница сумм в п.1. и п.2 есть число которое убрали.
Да нет, ты всё правильно понял, поэтому этап номер следующий: что делать, если убрали не одно, а два числа?
:)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 15:45:54.990000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
что делать, если убрали не одно, а два числа?
Будут несколько вариантов.
Найти способом Flint_ta разность X и найти все варианты:
1 и X-1
2 и X-2
3 и X-3
…
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 16:15:57.426666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Родригес
Будут несколько вариантов.
Найти способом Flint_ta разность X и найти все варианты:
1 и X-1
2 и X-2
3 и X-3
…
Эээ неее, вариант должен быть только один. У тебя есть один проход, чтобы просканировать все числа, и константное количество памяти, чтобы определить каких именно чисел не хватает.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 16:40:25.003333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
А, не понял сперва задачи, прошу прощения.
Когда я был сопливым ребенком, по соседству жил парень, лет на 10-12 старше, он показывал такой фокус - давал нам колоду карт, мы незаметно вытаскивали одну, потом, перемешав, отдавали ему. Он колоду с очень высокой скоростью по одной карте скидывал, а потом называл недостающую. Секрет так и не открыл, до сих пор не знаю, он как то считал или же запоминал все.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 16:42:19.866666
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Константое это сколько?
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 17:24:57.470000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: Родригес
Константое это сколько?
Независящее от исходного количества чисел. Твой алгоритм должен потреблять одинаковое количество памяти, вне зависимости от того, сто чисел в наборе, тысяча или мильён.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 19:02:45.253333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Пусть количество членов набора чисел - N , числа от 1 до N.
1 Находим сумму набора ∑=(1+N)N/2
2 Находим произведение всех членов N! ( Нет необходимости хранить все цифры числа, достаточно нескольких значащих цифр и порядка, например так: 2,6525285e+32. )
3 Последовательно считывая по одному элементу находим сумму и произведение оставшихся чисел
4 Разделив N! на произведение оставшихся чисел найдем произведение искомых двух чисел (после округления)
5 Отняв от ∑ сумму оставшихся чисел найдем сумму искомых двух
6 Нехитрая математика позволит из произведения и суммы найти два числа
Не совсем то, что говорил rgo, N ограничена количеством значащих цифр произведения.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 19:42:46.086666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: Родригес
Пусть количество членов набора чисел - N , числа от 1 до N.
1 Находим сумму набора ∑=(1+N)N/2
2 Находим произведение всех членов N! ( Нет необходимости хранить все цифры числа, достаточно нескольких значащих цифр и порядка, например так: 2,6525285e+32. )
3 Последовательно считывая по одному элементу находим сумму и произведение оставшихся чисел
4 Разделив N! на произведение оставшихся чисел найдем произведение искомых двух чисел (после округления)
5 Отняв от ∑ сумму оставшихся чисел найдем сумму искомых двух
6 Нехитрая математика позволит из произведения и суммы найти два числа
Да, особенно понравилось про "Нет необходимости хранить все цифры числа", как-то я об этом не подумал. Действительно, если мы будем считать произведение всех чисел по модулю 2^32, нам этого хватит. А умножение по модулю 2^32, это как раз то самое умножение unsigned int'ов, которое дают нам компиляторы (по-крайней мере бОльшая их часть).
Единственная проблема в том, что деление-то компиляторы выполняют не по модулю 2^32, и математика окажется, всё же, с хитростями. Кстати, может даже ничего и не выйдет, 2^32 – это не простое число, значит в кольце вычетов будут делители нуля, а это скорее всего приведёт к появлению множественных решений уравнения.
Считать же используя float, на мой взгляд не очень хорошо: там довольно-таки быстро мы получим переполнение. В single float, насколько я помню под показатель степени отводится восемь бит, причём знаковые восемь бит, значит максимальный множитель при мантиссе будет 2^127, а log[2](100!) ~= 524.765 > 127.
Но как бы там не было, мыслишь в правильном направлении. Нужно второе уравнение. Я бы предложил дополнительно к сумме всех чисел считать ещё сумму квадратов.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 21:38:46.660000
|
|
|
Jakeroid
Сообщений: 12
Оценки: 0
Присоединился: 2010-01-26 23:34:43.993333
|
rgo,
quote:
Единственная проблема в том, что деление-то компиляторы выполняют не по модулю 2^32, и математика окажется, всё же, с хитростями.
Я не опытный в программировании. Но помню, что компилятор сможет делить быстрее если использовать сдвиги. Тоесть перевести число в двоичный код, а потом сдвинуть. Вот что и куда, и как делить забыл. Извините.:)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-02 23:58:15.153333
|
|
|
disCoverall
Сообщений: 32
Оценки: 0
Присоединился: 2010-10-31 00:43:50.613333
|
quote:
rgo
Я бы предложил дополнительно к сумме всех чисел считать ещё сумму квадратов.
В принципе можно было бы модифицировать теорему ферма, было бы просто замечательно
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-03 12:41:02.260000
|
|
|
Davey
Сообщений: 45
Оценки: 0
Присоединился: 2010-03-24 14:51:57.760000
|
Kreol, за один проход, всмысле чтобы асимптотика была O(N) или чисто ОДИН проход + пару действий, то есть 2N не катит? >>
Кроме решений наподобие решения Родригеса вроде никак больше, если имеется в виду фиксированная память, это всмысле на всю программу, то есть входную последовательность тоже нельзя хранить?
А если сделать как у Родригеса, но с xor-ом. Вроде бы если все числа разные, то можно вторую ф-ю(после сложения) брать не умножение, а xor и не не должно сплющить…
Тогда в конце просто перебрать за линейное время варианты a b и подставлять их в выражение,
чтобы получилось что xor (a, b) = xor(всех между собой) xor (xor (тех что есть меж собой)).
Ну, разумеется xor всех между собой и тех что даны посчитаем один раз в начале и всё такое… Может я чего напутал?
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-03 15:12:11.600000
|
|
|
yurket
Сообщений: 69
Оценки: 0
Присоединился: 2009-05-04 23:47:54.993333
|
два уравнения:
1) a + b = x, где x = сумма_до - сумма_после
2) a^2 + b^2 = y, где y = сумма_квадратов_до - сумма_квадратов_после
решаем систему уравнений)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-03 17:59:36.783333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: yurket
два уравнения:
1) a + b = x, где x = сумма_до - сумма_после
2) a^2 + b^2 = y, где y = сумма_квадратов_до - сумма_квадратов_после
решаем систему уравнений)
А доказать единственность корней сможешь?
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-03 20:58:09.483333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
quote:
ORIGINAL: yurket
два уравнения:
1) a + b = x, где x = сумма_до - сумма_после
2) a^2 + b^2 = y, где y = сумма_квадратов_до - сумма_квадратов_после
решаем систему уравнений)
А доказать единственность корней сможешь?
А чего тут доказывать? Вот например геометрическое "доказательство". С точки зрения математики – это не доказательство, но с общечеловеческой покатит. Кому не покатит, пускай сочиняет либо чисто алгебраическое доказательство, либо допиливает сие геометрическое до нужных кондиций строгости.
Итак. Если нарисовать решения каждого уравнения в плоскости с осями a, b, то мы увидим, что картинка симметрична относительно прямой a=b. Второе уравнение – это окружность с центром в начале координат, первое же – прямая перпендикулярная прямой a=b. Очевидно, что прямая (1) будет пересекаться с окружностью (2) (у нас по определению системы там есть по-крайней мере одно решение). При этом прямая будет либо касаться окружности, либо пересекать её в двух точках.
Первый случай, когда прямая касается, на самом деле не имеет никакого отношения к нам. Если прямая будет касаться, то решение будет выглядеть как (a1, a1). Что будет означать что из набора удалили два одинаковых числа. Такого быть не может по условию задачи. Значит и прямая не будет касаться.
То есть определённо, прямая будет пересекать окружность в двух точках. Решений будет два, но в силу симметрии картинки, решения тоже будут симметричны. То есть если первое решение, это (a1, b1), то второе будет выглядеть как (b1, a1). И если мы вернёмся к условию задачи, мы увидим, что эти два решения, на самом деле для нас являются одним и тем же решением.
В принципе, чтобы было красивее, можно дополнить систему уравнений условием a<b.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-03 21:44:14.750000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Davey
Kreol, за один проход, всмысле чтобы асимптотика была O(N) или чисто ОДИН проход + пару действий, то есть 2N не катит? >>
Кроме решений наподобие решения Родригеса вроде никак больше, если имеется в виду фиксированная память, это всмысле на всю программу, то есть входную последовательность тоже нельзя хранить?
Обычно оба вопроса не имеют значения. Если тебе нужно собрать какую-то информацию о последовательности, уместившись в константную память, то всегда или почти всегда сделать это можно за один проход. Если тебе всё равно не разрешено бегать по всей последовательности много раз, то не вижу разницы между хранением в памяти или на диске/в сети/любым устройством с последовательным доступом. Но, если это тебе важно, то можешь использовать O(N) времени и хранить последовательность в памяти.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-03 21:51:37.816666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
А чего тут доказывать?
В общем-то, верно. Но тогда скажу и третью, последнюю часть задачи :)
Обобщить решение для k убранных чисел. То есть для 3-х, 4-х, 5-ти и т.д.
При этом память должна зависеть линейно только от k, а время - от k и N.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-03 23:26:47.486666
|
|
|
yurket
Сообщений: 69
Оценки: 0
Присоединился: 2009-05-04 23:47:54.993333
|
первое, что прихохдит в голову это составить k уравнений вида
a1^n + a2^n + … + ak^n = (сумма_чисел_в_степени_n_до - сумма_чисел_в_степени_n_после), 0 < n <= k
и решать систему из кучи уравнений неизвестно как =)
но это явно как-то не круто)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 00:08:56.866666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: yurket
первое, что прихохдит в голову это составить k уравнений вида
a1^n + a2^n + … + ak^n = (сумма_чисел_в_степени_n_до - сумма_чисел_в_степени_n_после), 0 < n <= k
и решать систему из кучи уравнений неизвестно как =)
но это явно как-то не круто)
Дело не в том круто или нет. Не видно способа уложиться по времени в O(k). Можно избавиться от этих степенных уравнений, получить систему уравнений второй степени, где каждое уравнение будет суммой членов вида a[и]*a[j]. Но толку то?
Ведь даже если мы получим систему линейных уравнений, для которых существуют отработанные методы решений, то время решения будет O(k^3). По крайней мере метод гаусса требует O(k^3), и AFAIR, быстрее никак. Даже если бы мы получили сходу верхнетреугольную матрицу системы (еслиб ещё знать как…), это был бы O(k^2). В случае таких степенных/второй-степени уравнений, я думаю ситуация будет ещё плачевнее.
ps. Почесав затылок, я пришёл к такой мысли: kreol, скорее всего, не случайно начал докапываться к доказательству единственности решения системы. Мы видать пошли не тем путём, на который он рассчитывал. ;)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 00:46:35.546666
|
|
|
disCoverall
Сообщений: 32
Оценки: 0
Присоединился: 2010-10-31 00:43:50.613333
|
rgo , монстр математики)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 09:40:51.910000
|
|
|
Davey
Сообщений: 45
Оценки: 0
Присоединился: 2010-03-24 14:51:57.760000
|
Если хранить последовательность в памяти, то впринципе что мешает отсортировать перестановку(а как известно перестановку элементов от 1 до N можно отсортировать за O(N), while максимум 2N раз выполнится : for(int i=0; i<n; i++) while(a[i] != i) swap(a[a[i]], a[i])... Ну и собственно после такой сортировки остается пройтись один раз по массиву и посмотреть на дыры.
Но Kreol наверно всё же хотел что-то другое, а так получается просто читерно… ^^
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 11:24:57.460000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Davey
Если хранить последовательность в памяти, то впринципе что мешает отсортировать перестановку(а как известно перестановку элементов от 1 до N можно отсортировать за O(N)
Эээ, не знаю, что ты понимаешь под сортировкой перестановки, но последовательность отсортировать на O(N) у тебя вряд ли получится ;)
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 12:10:41.216666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: kreol
При этом память должна зависеть линейно только от k, а время - от k и N.
Пардон, неясно выразился. Память должна линейно зависеть от k и не зависеть от N, время должно просто как-то зависеть от k, но не от N (не считая первого прохода). Смысл в том, что k - это всегда небольшое число, которым можно манипулировать как угодно. Поэтому решение за k^3 легально. Другое дело доказать, что корни при этом решении будут единственными )
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 16:08:30.033333
|
|
|
Davey
Сообщений: 45
Оценки: 0
Присоединился: 2010-03-24 14:51:57.760000
|
Перестановка - всмысле были числа от 1 до N и все разные и их переставили местами. Тогда каждое мы просто ставим на свое место за максимум 2N действий. А про последовательность из любых чисел я и не заикался что за O(N), ничего не подумайте там^^
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 18:38:11.363333
|
|
|
yurket
Сообщений: 69
Оценки: 0
Присоединился: 2009-05-04 23:47:54.993333
|
а как предложение детектить на каджом шаге сумму текущих членов и сравнивать ее с суммой, которая должна быть без удаления?
1) цикл от 1 до n
2) Sn = (1+n)*n/2
3) Sn' = Sn' + n;
4) если Sn' == Sn то след. итерация,
если Sn' != Sn то явно было удалено число… или несколько чисел, идущих по порядку… в первом случае это одно n, тогда Sn' будет больше Sn на 1… во втором случае если, например, Sn' > Sn на 5, то значит было удалено 5 чисел, начиная с n…
5) записываем удаленное число (числа)…
6) устанавливаем Sn' = Sn, и на след. итерацию…
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-04 23:17:01.546666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Насколько я понимаю, числа могут быть перетасованы. Иначе задачи бы не было, она решалась бы элементарно.
|
|
|
|
|
RE: Задача: пропавшее число - 2010-11-06 21:39:45.956666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
Насколько я понимаю, числа могут быть перетасованы. Иначе задачи бы не было, она решалась бы элементарно.
Верно.
|
|
|
|
|
|
