С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/10: Рейтинг темы: голосов - 10, средняя оценка - 5.00
tyomaart
0 / 0 / 0
Регистрация: 01.11.2013
Сообщений: 4
1

Поиск отсутствующего целого числа

07.01.2015, 01:03. Просмотров 1938. Ответов 37
Метки нет (Все метки)

Массив A[1..n] содержит все целые числа от 0 до n за исключением одного. Отсутствующее число можно легко определить за время О(n), располагая вспомогательным массивом B[1..n], предназначенным для записи имеющихся чисел из массива А. Однако, в этой задаче мы лишены средств, позволяющих получить доступ к целому числу из маcсива А посредством одной операции. Элементы массива А представлены в двоичной системе счисления, и единственаая операция, с помощью которой можно осуществлять к ним доступ, это "извлечение j-го бита элемента А[i]" , которая выполняется в течение фиксированного времени .
Покажите,что , распологая только этой операцией, отсутствующее челое число все же можно определить за время O(n).
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2015, 01:03
Ответы с готовыми решениями:

Поиск по вектору наименьшего отсутствующего элемента
В общем, есть вектор, в нем хранятся значения типа <unsigned int>. Как за...

Описать функцию DigitN(K, N) целого типа, возвращающую N-ю цифру целого положительного числа K
Помогите выполнить задание. Описать функцию DigitN(K, N) целого типа,...

Определить цифры целого числа (тип числа - целое без знака)
Определить цифры целого числа( тип числа-целое без знака), вычислить сумму...

Из целого числа получить новое, состоящее из нечетных цифр числа (2315663 -> 3153)
Из целого числа получить новое, состоящее из нечетных цифр числа (2315663 ->...

Конструирование значения целого числа или числа с плавающей точкой по его дампу
Как сконструировать значения целого числа(char, short int, long int) или числа...

37
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
07.01.2015, 01:12 2
Думаю _Ivana захотел бы над ней подумать и увидеть красивое решение
Попозже поделюсь своими мыслями
0
_Ivana
3237 / 1870 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
07.01.2015, 01:35 3

Не по теме:

Только пришел с катка, пол второго ночи - самое время залезть с ванну с потертой липовачей, а тут очередная задачка :)

За 5 минут ничего особо красивого не придумал кроме того, что если мы рассматриваем массив из битовых полей постоянной конечной разрядности, то каждое число можно побитово за О(1) взять, значит и задача решается за О(n). Но наверное составителем предполагалось что-то поинтереснее. А если учитывать, что с увеличением n количество необходимых разрядов для хранения чисел от 0 до n также возрастает (пусть логарифмически, но все же), то я немножко сомневаюсь в справедливости тезиса, который необходимо доказать. Но подумаю еще на досуге.
0
tyomaart
0 / 0 / 0
Регистрация: 01.11.2013
Сообщений: 4
07.01.2015, 01:46  [ТС] 4
Дали этот код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<string>
#include<vector>
#include <ctime>
//---------------------------------------------------------------------------
using namespace std;
int main()
{
string a[10];
int r;
cin>>r; // КОЛИЧЕСТВО ЭЛЕМЕНТОВ
vector<int> v1;
vector<int> v2;
vector<int> v3; // Нужные к рассмотрению строки
string s2;
 
//                БЛОК ИНИЦИАЛИЗАЦИИ МАССИВА
//--------------------------------------------------------
int n=0; int p=0;
for(int i=0;i<r;i++)
        {
         cin>>a[i];
        }
for(int i=0;i<r;i++)
v3.push_back(i);
//--------------------------------------------------------
//                    БЛОК ПОИСКА
//--------------------------------------------------------
for(int j=a[1].size()-1;j>=0;j--)
        {
        if(v3.size() == 1)
                {
             //   cout << v3[0] << ' ' <<a[v3[0]][0] << endl;
                        if(a[v3[0]][0] == '0')
                        {
                                s2=s2+'1';
                        }
                                else
                                {
                                s2=s2+'0';
                                }
                }else
{
        for(int i=0;i<v3.size();i++)
                {
                if(a[v3[i]][j] == '0'){
                        n++;v1.push_back(i);}
                                else{
                                        p++;v2.push_back(i);}
                 }
                int d=a[1].length()%2;
                if(n == p){
                        if(d != 0){
                                s2=s2+'0'; v3.swap(v1);v1.clear();v2.clear();}
                                        else{
                                                s2=s2+'1'; v3.swap(v2);v1.clear();v2.clear();}
                          }
                else{
                     if(n>p)
                        {
                        s2=s2+'1';
                        v3.swap(v2);
                        v2.clear();
                        v1.clear();
                        }
                     else
                        {
                        s2=s2+'0';
                        v3.swap(v1);
                        v1.clear();
                        v2.clear();
                        }
                        }
                n=0;p=0;}
 
}
int k=s2.length();
for(int i=k;i>0;i--)
cout<<s2[i-1];
cout<<clock()/1000.0<<endl;
system("pause");
        return 0;
}
//---------------------------------------------------------------------------
Но он ниф**а не работает. А что делает и подавно...
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
07.01.2015, 10:07 5
Цитата Сообщение от _Ivana Посмотреть сообщение
что с увеличением n количество необходимых разрядов для хранения чисел от 0 до n также возрастает
Думаю, что кол-во разрядов остается константой.
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 10:17 6
Dani, скажешь решение?
0
TrueTerm
169 / 117 / 45
Регистрация: 25.12.2014
Сообщений: 385
07.01.2015, 10:40 7
Цитата Сообщение от tyomaart Посмотреть сообщение
Отсутствующее число можно легко определить за время О(n), располагая вспомогательным массивом B[1..n], предназначенным для записи имеющихся чисел из массива А.
Если бы не ограничение на двоичный доступ, найти отсутствующее число было бы очень просто и без вспомогательного массива.
Сумма всех чисел от 0 до n равна (0+n)(n+1)/2. Можно было бы подсчитать сумму всех чисел в массиве (за О(n) операций) и вычесть её из (0+n)(n+1)/2.
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 10:45 8
TrueTerm, я прост не пойму что дает это ограничение на 2 доступ? то, что мы не можем за О(1) вычислить само число, зная его 2-ый эквивалент?
0
Enno
267 / 170 / 40
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
07.01.2015, 10:53 9
Опять ляпнул не подумав.
0
TrueTerm
169 / 117 / 45
Регистрация: 25.12.2014
Сообщений: 385
07.01.2015, 10:54 10
Аналогично, можно посчитать несколько сумм поразрядно (по каждому разряду) и вычесть получившееся из F(n,j)="количество единиц в j-м разряде столбика двоичных чисел от 0 до n". Можно вместо поразрядной суммы считать Sj- "сумму в j-м разряде по модулю 2 (XOR)". Тогда j-й разряд отсутствующего числа определится как Sj xor G(n,j). Где G(n,j)={1,если количество единиц в j-м разряде столбика двоичных чисел от 0 до n чётно; 0, иначе}.
Итого имеем O(n) операций по каждому из k разрядов, что ~ O(n).
0
Enno
267 / 170 / 40
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
07.01.2015, 10:55 11
извлечение j-го бита элемента А[i]
А "отсутствует" значит равно нулю?
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 10:55 12
TrueTerm, это N * log(N)
0
TrueTerm
169 / 117 / 45
Регистрация: 25.12.2014
Сообщений: 385
07.01.2015, 11:00 13
Цитата Сообщение от Enno Посмотреть сообщение
Из суммы целых чисел от 0 до n вычесть сумму чисел массива = отсутствующее число. Это при условии что "отсутствует" == 0.
Пусть в массиве 0,1,2,3,4 отсутствует 2. Сумма всех чисел 0+1+2+3+4=10. А если 2 отсутствуют, то 0+1+3+4=8. Отсутствующее 10-8=2.
Так для любого числа, не только для нуля. Для отсутствующего нуля: 10-10=0 -отсутствующее число.

Добавлено через 1 минуту
Цитата Сообщение от SlavaSSU Посмотреть сообщение
TrueTerm, это N * log(N)
А, ну да. разрядность зависит от N тоже. Но мне кажется, что k предполагается фиксированым.
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 11:02 14
TrueTerm, тогда эта тупая задача. если длину чисел считать константой, то что тогда мешает взять и перевести все числа в 10-ую систему, а дальше делай с ними че хочешь.
0
Enno
267 / 170 / 40
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
07.01.2015, 11:02 15
Массив A[1..n]
от 0 до n
Не клеится.
Если числа идут подряд:
Число чисел со старшим ненулевым битом будет увеличиваться в геометрической прогрессии в зависимости от разряда в котором бит установлен. Сверху вниз пройтись, если где разрыв, череда единиц заканчивается когда не равна степени двойки, та ячейка массива, где единица не выставлена (в первый раз), является искомым нулём.

Вообще приведите пример "отсутствующего" числа.
012345 - полный ряд
1) 012335
2) 012305
3) 01235
Какой из вариантов?
0
TrueTerm
169 / 117 / 45
Регистрация: 25.12.2014
Сообщений: 385
07.01.2015, 11:09 16
Цитата Сообщение от SlavaSSU Посмотреть сообщение
TrueTerm, тогда эта тупая задача. если длину чисел считать константой, то что тогда мешает взять и перевести все числа в 10-ую систему, а дальше делай с ними че хочешь.
Для перевода чисел в 10-ю надо их считать из массива, а для этого понадобится операция извлечения 2-ного разряда ,которая выполняется за фиксированное время. Вот это и помешает.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
07.01.2015, 11:15 17
Цитата Сообщение от TrueTerm Посмотреть сообщение
Для перевода чисел в 10-ю надо их считать из массива, а для этого понадобится операция извлечения 2-ного разряда ,которая выполняется за фиксированное время. Вот это и помешает.
А как работать с числом если будет известна только половина его разрядов?
0
TrueTerm
169 / 117 / 45
Регистрация: 25.12.2014
Сообщений: 385
07.01.2015, 11:15 18
Цитата Сообщение от Enno Посмотреть сообщение
Если числа идут подряд:
Нигде не сказано "идут подряд", сказано "есть все числа, кроме одного". Недостающее число можно считать как замененное нулём. Тогда в каждом разряде пропадёт одна единица, если в недостающем числе была в этом разряде единица. Поэтому чётность в столбике этого разряда изменится. А если у искомого числа был в этом разряде 0, то чётность останется такой же. Вот по этому признаку и можно найти все разряды числа.
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 11:16 19
TrueTerm, кого считать из массива?
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
07.01.2015, 11:18 20
Я видел как самое хорошее решение - через xor
И как раз биты могут пригодиться.
0
07.01.2015, 11:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2015, 11:18

нужен тип целого числа для числа 19!= 121 645 100 408 832 000
Нужно посчитать сумму цифр целого положительного числа. double...

Дана строка. Определить, представляет ли она собой запись целого числа или запись дробного числа
Дана строка.Необходимо определить ,представляет ли она собой запись целого...

. Дана строка, изображающая десятичную запись целого положительного числа. Вывести строку, изображающую двоичную запись этого же числа
срочно помогите пожалуйста


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru