Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.67/15: Рейтинг темы: голосов - 15, средняя оценка - 4.67
16 / 16 / 12
Регистрация: 27.05.2014
Сообщений: 133
1

Отобразить минимальное положительное число, которое невозможно представить в виде суммы элементов массива

11.01.2016, 18:48. Просмотров 2851. Ответов 52
Метки нет (Все метки)

Отобразить то минимальное положительное число, которое невозможно представить в виде суммы элементов массива. Количество действий O(n^2).

Кто может помочь с задачей? Заранее спасибо.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.01.2016, 18:48
Ответы с готовыми решениями:

Найти наименьшее целое положительное число, которое нельзя представить в виде суммы нескольких элементов массива
Дан неубывающий массив положительных целых чисел a≤a≤…≤a. Найти наименьшее целое положительное...

Найти наименьшее целое положительное число, которое нельзя представить в виде суммы нескольких элементов массива
Не выходит.....:) Дан неубывающий массив положительных целых чисел a≤a≤…≤a....

Найти наименьшее целое положительное число, которое нельзя представить в виде суммы нескольких элементов массива
Блин, даже и не ожидала, что кто-то ответит на мою предыдущую задачу, а оказалось, что ответили...

Найти наименьшее число, которое нельзя представить в виде суммы нескольких элементов массива
Lан неубывающий массив положительных целых чисел a≤a≤…≤a. Найти наименьшее целое положительное...

52
Эксперт C
24585 / 15199 / 3217
Регистрация: 24.12.2010
Сообщений: 32,639
11.01.2016, 19:39 2
Арен, Что известно о массиве?
0
16 / 16 / 12
Регистрация: 27.05.2014
Сообщений: 133
11.01.2016, 19:59  [ТС] 3
Байт, Что элементы положительные.
0
Комп_Оратор)
Эксперт по математике/физике
8420 / 4182 / 569
Регистрация: 04.12.2011
Сообщений: 12,440
Записей в блоге: 14
11.01.2016, 21:32 4
Арен, я думаю что речь идёт о положительных целых числах и следовательно искомое число на единицу меньше суммы минимального и... следующего минимального элементов.
0
16 / 16 / 12
Регистрация: 27.05.2014
Сообщений: 133
11.01.2016, 21:45  [ТС] 5
IGPIGP, Вот решения бы не помешало, а то в голову ничего не приходит.
0
44 / 20 / 6
Регистрация: 28.02.2013
Сообщений: 194
11.01.2016, 21:54 6
условие какоето расплывчатое. в искомой сумме каждый элемент надо использовать сколько раз?
(0-1)?
(0-бесконечности)?

Добавлено через 3 минуты
кстати в обоих вариантах ответ тривиален.
если каждый элемент можно использовать сколько угодно раз) - то если там нет единицы - то ответ = 1ж если там есть 1 - то ответа нет в принципе.
если же можно только 1 раз использовать каждое число - то...
0
Комп_Оратор)
Эксперт по математике/физике
8420 / 4182 / 569
Регистрация: 04.12.2011
Сообщений: 12,440
Записей в блоге: 14
11.01.2016, 21:54 7
Цитата Сообщение от Арен Посмотреть сообщение
IGPIGP, Вот решения бы не помешало, а то в голову ничего не приходит.
!!!?
Это как? Вообще, не нужно что бы приходило всё. Но найти эту пару при 0(n2) это хоть пузырём отсортировать (по возрастанию для определённости) а потом сложив два первых и вычесть единицу. Затем убедиться что результат неотрицателен (если отрицателен, то напечатать "Не-а").
зы Он будет отрицателен если в массиве есть пара и более нулей.
0
16 / 16 / 12
Регистрация: 27.05.2014
Сообщений: 133
11.01.2016, 21:54  [ТС] 8
nefton, Один раз.
0
44 / 20 / 6
Регистрация: 28.02.2013
Сообщений: 194
11.01.2016, 22:26 9
есть мысль мега быстрого алгоритма, намного быстрее поставленных лимитов (хоть я и неочень понимаю в этих O(n^2))
Сейчас изложу в программе.

Добавлено через 25 минут
блин мегабыстро не получилось. можно только прямым перебором но это иттераций = 2^размермассива
0
16 / 16 / 12
Регистрация: 27.05.2014
Сообщений: 133
11.01.2016, 22:27  [ТС] 10
nefton, Медленно запускается?
0
Комп_Оратор)
Эксперт по математике/физике
8420 / 4182 / 569
Регистрация: 04.12.2011
Сообщений: 12,440
Записей в блоге: 14
11.01.2016, 22:29 11
Цитата Сообщение от nefton Посмотреть сообщение
2^размермассива
Там ещё одно сравнение во второй итерации)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main()
{
    int a[]={2,1,3,5,7,6,4};
int sizeAr=sizeof(a)/sizeof(a[0]);
int fmin_ind=0, smin_ind=0;
for(int i=0; i<sizeAr; i++)
if(a[fmin_ind]>a[i])fmin_ind=i;
 
for(int i=0; i<sizeAr; i++){
if(i==fmin_ind)continue;
if(a[smin_ind]>a[i])smin_ind=i;
}
int res=a[fmin_ind]+a[smin_ind]-1;
if(res>0)cout<<res;//2=1+2-1
else cout<<"nop...";
    cout<<endl;
system("pause");
    return 0;    
}
0
16 / 16 / 12
Регистрация: 27.05.2014
Сообщений: 133
11.01.2016, 22:34  [ТС] 13
nefton, Насчет неубывания речи не идет.

Добавлено через 13 секунд
IGPIGP, А почему отображает 2?
0
44 / 20 / 6
Регистрация: 28.02.2013
Сообщений: 194
11.01.2016, 22:41 14
сортировать массив по возрастанию - это самая меньшая из проблем. и занимает времени понт.
дело пойдёт веселее если опубликовать какието примеры входных данных и как примерно оценивать скорость расчёта.
0
Эксперт C
24585 / 15199 / 3217
Регистрация: 24.12.2010
Сообщений: 32,639
11.01.2016, 23:04 15
nefton, Вторая ссылка - просто чепуха. Первая даже если и решает задачу (в чем сомневаюсь), то совсем не ту.
Самый "хороший" массив - состоящий из степеней двойки 1 2 4 8 16 ...2n. Для него ответ 2n+1. Это вообще максимально-возможное. Понятно, что "разрывы" в этом массиве резко уменьшают искомое число. А "сжатия" - тоже уменьшают. Вот как-то отсюдова плясать...
0
Комп_Оратор)
Эксперт по математике/физике
8420 / 4182 / 569
Регистрация: 04.12.2011
Сообщений: 12,440
Записей в блоге: 14
11.01.2016, 23:10 16
Цитата Сообщение от Арен Посмотреть сообщение
А почему отображает 2?
А Вы как думаете? Я думаю что 2
Цитата Сообщение от Арен Посмотреть сообщение
невозможно представить в виде суммы элементов массива
2,1,3,5,7,6,4
и это максимальное положительное число из тех которые
Цитата Сообщение от Арен Посмотреть сообщение
невозможно представить в виде суммы элементов массива
2,1,3,5,7,6,4
кстати в Вашем условии сказано:
Цитата Сообщение от Арен Посмотреть сообщение
Отобразить то минимальное положительное число, которое невозможно представить в виде суммы элементов массива.
А это значит:
Цитата Сообщение от Арен Посмотреть сообщение
Отобразить минимальное положительное число
то есть
C++
1
cout<<'1';
Тогда весь текст (с указанием сложности алгоритма) - мусорехидная загадка. Я отметаю такой вариант.
0
Эксперт C
24585 / 15199 / 3217
Регистрация: 24.12.2010
Сообщений: 32,639
11.01.2016, 23:16 17
Цитата Сообщение от IGPIGP Посмотреть сообщение
А Вы как думаете?
Я думаю, что для приведенного массива минимальное число = 29.
Сумма из одного числа - тоже сумма! Иначе (если пренебречь этим очевидным математическим фактом), действительно
Цитата Сообщение от IGPIGP Посмотреть сообщение
ехидная загадка
1
44 / 20 / 6
Регистрация: 28.02.2013
Сообщений: 194
11.01.2016, 23:17 18
IGPIGP, задача поставлена более менее корректно и она не ерунда.
у тебя есть некоторое количество монеток разного номинала. и надо найти какое минимальное число ты не сможешь из них выложить. (в смысле сумма денег)
1
Комп_Оратор)
Эксперт по математике/физике
8420 / 4182 / 569
Регистрация: 04.12.2011
Сообщений: 12,440
Записей в блоге: 14
11.01.2016, 23:48 19
Цитата Сообщение от Байт Посмотреть сообщение
Сумма из одного числа - тоже сумма!
Не бывает. Может быть сумма числа и... числа. Даже если это ноль. Я нигде не видел суммы представленной одним слагаемым. То есть в самых общих формулировках:
Цитата Сообщение от Байт Посмотреть сообщение
Сумма из одного числа - тоже сумма!
это просто эмоция.
А в контексте задачи и тем паче. Зачем слово "сумма" тогда, если можно было сказать "элемент"?
Цитата Сообщение от nefton Посмотреть сообщение
задача поставлена более менее корректно и она не ерунда.
Текст который я вижу некорректен, как я думаю.
Цитата Сообщение от nefton Посмотреть сообщение
найти какое минимальное число ты не сможешь из них выложить
минимальное которое я не смогу из них выложить (используя минимум 2 шт.) это единица. Оно минимальное и его нельзя выложить из положительной пары. Я понимаю Ваш вариант условия, но словами его выразить нужно бы не так как в условии, а по другому. Например найти число, которое меньше минимальной суммы составленной из элементов... Я кстати так и понял условие судя по коду.
Однако если переформулировать условие в:
Цитата Сообщение от Арен Посмотреть сообщение
то максимальное положительное число, которое невозможно представить в виде суммы элементов
то всё усложняется.
Поэтому не будем торопиться, подождём ответа ТС.
0
44 / 20 / 6
Регистрация: 28.02.2013
Сообщений: 194
12.01.2016, 00:16 20
Цитата Сообщение от IGPIGP Посмотреть сообщение
(используя минимум 2 шт.)
ты в магазине расплачиваешся минимум 2мя купюрами?

Добавлено через 2 минуты
по теме, вот тупой перебор массив до 23 элементов (больше - писанина усложняется)
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
#include <iostream>
 
using namespace std;
 
 
bool Vozmoznost_pereborom(int* Nomera, int size, int number){
 
    unsigned long magik = 0;
 
    unsigned long max_magik = 1 << (size + 1);
 
    while (magik != max_magik ){
 
        magik++;
        int summ = 0;
        for (int i = 0; i < size; i++) {
            if (magik&(1 << i)) {
                summ += Nomera[i];
            }
        }
 
        if (summ == number) {
            //cout << number << ":" << magik << endl;
            return true;
        }
    }
    
    return false;
}
 
 
 
int main()
{
    const int size = 7;
    
    int Arr[size] = { 2, 1, 3, 5, 7, 6, 4 };
    
    int number_to_find = 0;
 
    while (true){
        
        number_to_find++;
        if (!Vozmoznost_pereborom(Arr, size, number_to_find)){
            cout << number_to_find;
            break;
        }
 
    }
 
    
 
 
 
 
 
    cout << endl << endl;
    system("pause");
    return 0;
}
Добавлено через 4 минуты
да и 2 в степени 24 этот алгоритм замориться перебирать

Добавлено через 4 минуты
можно использовать мелкие хаки типа сортировать массив чисел по возрастанию и использовать для перебора не весь массив, а только до определённого элемента большего искомого числа. Но это не решит главную проблемму, один фиг он сломается на массиве
1 2 4 8 16 32 64 128 256 512 1024 2048 ... раз 50 и ниодин суперкомпьютер не решит задачу никогда.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2016, 00:16

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Определить наименьшее натуральное число, которое невозможно представить в виде суммы данных чисел
Дано N целых чисел. Необходимо определить наименьшее натуральное число, которое невозможно...

Натуральное число X представить в виде суммы некоторых элементов массива
Само условие: Задан линейный массив N различных натуральных чисел (N ≤ 15). Определить,...

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

Определить наименьшее число, которое можно представить в виде суммы a^n+b^n по крайней мере двумя различными способами
Для заданного натурального N определить наименьшее число S, которое можно представить в виде суммы...


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

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

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