Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
tyomaart
0 / 0 / 0
Регистрация: 01.11.2013
Сообщений: 4
#1

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

07.01.2015, 01:03. Просмотров 1772. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Поиск отсутствующего целого числа (C++):

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

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

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

Конструирование значения целого числа или числа с плавающей точкой по его дампу - C++
Как сконструировать значения целого числа(char, short int, long int) или числа с плавающей точкой(float,double) по его дампу(bin,oct,hex)??

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

нужен тип целого числа для числа 19!= 121 645 100 408 832 000 - C++
Нужно посчитать сумму цифр целого положительного числа. double summacifr(double chislo) { double summa=0; while(chislo) ...

37
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
07.01.2015, 01:12 #2
Думаю _Ivana захотел бы над ней подумать и увидеть красивое решение
Попозже поделюсь своими мыслями
0
_Ivana
3229 / 1857 / 157
Регистрация: 01.03.2013
Сообщений: 5,086
Записей в блоге: 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 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
07.01.2015, 10:07 #5
Цитата Сообщение от _Ivana Посмотреть сообщение
что с увеличением n количество необходимых разрядов для хранения чисел от 0 до n также возрастает
Думаю, что кол-во разрядов остается константой.
0
SlavaSSU
217 / 162 / 45
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 10:17 #6
Dani, скажешь решение?
0
TrueTerm
168 / 116 / 38
Регистрация: 25.12.2014
Сообщений: 384
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 / 45
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 10:45 #8
TrueTerm, я прост не пойму что дает это ограничение на 2 доступ? то, что мы не можем за О(1) вычислить само число, зная его 2-ый эквивалент?
0
Enno
267 / 170 / 38
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
07.01.2015, 10:53 #9
Опять ляпнул не подумав.
0
TrueTerm
168 / 116 / 38
Регистрация: 25.12.2014
Сообщений: 384
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 / 38
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
07.01.2015, 10:55 #11
извлечение j-го бита элемента А[i]
А "отсутствует" значит равно нулю?
0
SlavaSSU
217 / 162 / 45
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 10:55 #12
TrueTerm, это N * log(N)
0
TrueTerm
168 / 116 / 38
Регистрация: 25.12.2014
Сообщений: 384
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 / 45
Регистрация: 17.07.2012
Сообщений: 587
07.01.2015, 11:02 #14
TrueTerm, тогда эта тупая задача. если длину чисел считать константой, то что тогда мешает взять и перевести все числа в 10-ую систему, а дальше делай с ними че хочешь.
0
Enno
267 / 170 / 38
Регистрация: 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
07.01.2015, 11:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2015, 11:02
Привет! Вот еще темы с ответами:

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

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

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

Запись целого числа на С - C++
Условие: Определить, является ли данная последовательность символов правильной записью целого числа (возможно, со знаком)


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

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

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