Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > несложная задачка

Автор: Alek86 11.11.2007, 11:51

не знаю, насколько тут приветствуются подобные задачки, но... Есть массив из N чисел. 1. Он заполняется числами так:     - числа эти лежат в пределах [1; N]     - никогда не повторяются     - в случайном порядке (к примеру для N == 5 массив может иметь вид {2, 5, 3, 1, 4}) 2. Одно (любое) из чисел меняется на N + 1. (для преведенного выше примера это может быть {2, 5, 3, 6, 4}) 3. Программе на вход подается полученный массив ({2, 5, 3, 6, 4}). Она должна определить, какое число заменили. Как можно быстрее. Ответом должен быть код на С++, реализующий "поиск". ЗЫ. кому задача покажется слишком легкой, прошу без комментариев - тут не только гении программизма бывают

Автор: JackYF 11.11.2007, 12:22

Alek86, это в "Интересные задачи по программированию", имхо.

Автор: Alek86 11.11.2007, 12:32

да? не знал, что есть  извиняюсь

Автор: Fazil6 11.11.2007, 12:40

не понял в чем подвох... вариант Код int  index_detect(int *array, int size) {     for(int i = 0; i < size ; ++i)     {         if(array[i] > size) return i;     }      return -1; } недостаточно быстр?

Автор: Alek86 11.11.2007, 12:46

Цитата(Fazil6 @  11.11.2007,  12:40 ) не понял в чем подвох... для  {2, 5, 3, 6, 4} твоя программа выведет 3, а не 1, как требовалось нужно не индекс, а ЧИСЛО определить

Автор: MAKCim 11.11.2007, 12:54

Alek86,  Код int data[MAX_COUNT + 1]; int detect(int * array, int size) {     for (int index = 0; index < size; ++index)         data[array[index] - 1] = 1;     for (index = 0; index < size; ++index)         if (!data[index])             return index + 1; } итого O(n) + O(n) = 2 * O(n) ~ O(n)

Автор: Alek86 11.11.2007, 12:57

идея засчитана. может кто ЕЩЕ лучше найдет?

Автор: Fazil6 11.11.2007, 13:04

Цитата(Alek86 @  11.11.2007,  12:46 ) для  {2, 5, 3, 6, 4} твоя программа выведет 3, а не 1, как требовалось а... я подумал, что нужно индекс определить

Автор: MAKCim 11.11.2007, 13:07

Код int detect(int * array, int size) {     int s = 0;     for (int i = 0; i < size; ++i)         s += array[i];     return size - (s - size * (size + 1) / 2) + 1 } итого O(n) Добавлено через 4 минуты и 38 секунд думаю, оптимальный вариант

Автор: Alek86 11.11.2007, 13:12

я ж говорил, несложная быстро нашел

Автор: Dov 11.11.2007, 18:58

Цитата(Alek86 @  11.11.2007,  11:57 ) может кто ЕЩЕ лучше найдет? Не знаю, лучше или нет, но тоже вариант.    Код int detect(int * array, int size) {     int s = *array ^ 1;     for (int i = 1; i < size; ++i)         s ^= array[i] ^= i + 1;     return s ^ i + 1; }

Автор: Alek86 11.11.2007, 19:29

Цитата(Dov @  11.11.2007,  18:58 ) Не знаю, лучше или нет, но тоже вариант. ёпрст проверил, работает. но КАК, даже разбираться не хочется... если хотел как можно злостней решение придумать, ты цели достиг ;)

Автор: bsa 11.11.2007, 19:38

Dov, вариант MAKCim, имхо, быстрей. Скорость выполнения XOR равна скорости выполнения сложения, а у тебя арифметических операций в 3 раза больше в каждой итерации цикла. Хотя, для малых массивов твой вариант быстрее будет за счет отстуствия умножения (деление не считаю - любой порядочный компилятор обязан заменить его на сдвиг).

Автор: Dov 11.11.2007, 22:24

Цитата(Alek86 @  11.11.2007,  18:29 ) если хотел как можно злостней решение придумать, ты цели достиг ; Alek86, ты чего?   Это самое простое решение, которое пришло мне в голову.    Где-то здесь, на форуме(и не только на этом)  есть похожая задача, где нужно в массиве, состоящем из нескольких пар одинаковых чисел и одного непарного, например: {1,3,4,2,3,5,2,1,4}, найти это самое непарное число.  Так проще всего она решается именно этим способом. Проходим ХОR`ом весь массив и на выходе получаем искомое число. Что я и сделал.    Цитата(bsa @  11.11.2007,  18:38 ) Dov, вариант MAKCim, имхо, быстрей. bsa, вполне возможно. Я хронометраж не делал.    Цитата(bsa @  11.11.2007,  18:38 ) Хотя, для малых массивов твой вариант быстрее будет за счет отстуствия умножения (деление не считаю - любой порядочный компилятор обязан заменить его на сдвиг). bsa, а для больших массивов(на пару миллионов) у меня не  будет такой траблы, например: Код  for (int i = 0; i < size; ++i)         s += array[i];    // cout << s; Догадываешься?

Автор: DKroshkin 11.11.2007, 22:25

Вроде задача простая на знание арифметической прогрессии. Формул к сожалению не помню (учился давно, если надо могу вспомнить) 1. Бежишь по массиву, считаешь сумму, и вычисляешь кол-во элементов в массиве. 2. Вычисляешь сумму арифметической прогрессии 3. Вычитаешь из суммы, полученной в первом пунке сумму арифм. прогрессии и еще вычитаешь N (кол-во элементов) - это и будет искомое число. Скорость вычисления O(N)

Автор: Nat 12.11.2007, 11:42

Код int Funct( int *array, int size ) {         int sum1, sum2, i;         sum1 = 0;         sum2 = 0;         for(i = 0; i<size; i++)         {                 sum1 += i;                 if( array[i] <= size )                           sum2 += array[i];         }         return( (sum2 - sum1 )+1); }

Автор: MAKCim 12.11.2007, 11:48

Nat,  возьми массив {4, 2, 3} у тебя будет вывод 7 а надо 1 + для суммы арифметической прогрессии есть формула и не за чем вычислять ее в цикле

Автор: xvr 12.11.2007, 15:26

Пардон, неправильно прочел условия :(

Автор: DKroshkin 12.11.2007, 18:30

Код int calculate(int *values, int size) {     int sum1 = 0;     int sum2 = 0;     for (int i = 0; i < size; i++) {         sum1 += i + 1;         sum2 += values[i];     }     return size + 1 - (sum2 - sum1); } Не проверял, но должно работать

Автор: Alek86 12.11.2007, 18:40

вроде, верно жаль, ты не первый

Автор: Nat 13.11.2007, 08:42

Sorry, исправила :-[ Теперь должно правильно считать.

Автор: DKroshkin 13.11.2007, 09:59

Цитата(Alek86 @ 12.11.2007,  18:40) вроде, верно жаль, ты не первый  Ага обидно. прочитал всю ветку и нашел формулу для вычисления арифм. прогрессии. ))

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)