Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.52/21: Рейтинг темы: голосов - 21, средняя оценка - 4.52
21 / 21 / 16
Регистрация: 30.09.2013
Сообщений: 262

Перебор сумм чисел массива

12.11.2014, 00:23. Показов 4337. Ответов 16
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Собственно по одному предмету делаю курсач, и хотелось бы себя наверняка перепроверить, да и попрактиковать лишний раз C++.

Нужно грамотно научить программу перебирать массив следующим образом:
Есть любые числа, например:
1, 8, 4, 2
Есть последовательность чисел:
0
1
2
...
8
9

Получается некая таблица размером 4*10

Нужно следующее:
Беру 0 из столбика и смотрю какие числа рядка мне надо взять что бы получить 0? Соответственно никакое не нужно, ставлю четыре нуля (0 0 0 0) (смотрите ниже)
Беру 1 из столбика и смотрю какие числа рядка мне надо взять что бы получить 1? Соответственно беру 1 и на пересечение ставлю 1 0 0 0
.........
Беру 7 из столбика и смотрю какие числа рядка мне надо взять что бы получить 7? Соответственно беру сумму 1, 2 и 4 и на пересечение ставлю 1 0 1 1
.........

В конце получится должна получится таблица:
* 1 8 4 2
0|0 0 0 0
1|1 0 0 0
2|0 0 0 1
3|1 0 0 1
4|0 0 1 0
5|1 0 1 0
6|0 0 1 1
7|1 0 1 1
8|0 1 0 0
9|1 1 0 0

Как мне научить этому программу?

Я бы мог написать программу привязанную к 4м переменным, но а если мне надо будет больше переменных?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
12.11.2014, 00:23
Ответы с готовыми решениями:

Полный перебор чисел массива
Доброго вам времени суток. Количество элементов массива задавать вручную - собственно N. Массив заполняется числами от 1 до N. Стоит...

Перебор массива и поиск повторяющихся чисел
День добрый, подскажите пожалуйста, задача следующая, имеем массив {1,2,3,9,4,5,6,9,7,8,0}, тут девятка встречается два раза, необходимо...

Массив из сумм чисел исходного массива
Дано a={15,2,0,4,-15,-7,0,-44,0,-4} массив. Создать новый b массив у которого элементы должны быть так b1=a1, b2=a1+a2; b3=...

16
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
12.11.2014, 09:05
-MaZaHaKa-, сколько строк и столбцов будет максимум? И до скольки числа?
0
 Аватар для SmittWesson
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 09:22
Цитата Сообщение от SlavaSSU Посмотреть сообщение
И до скольки числа?
Не трудно подсчитать, что комбинация сумм всех цифр исходной строки будет N! и как следствие, ограничена либо временем вычислений, либо размером оперативки. То-же относится и к количеству строк.
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
12.11.2014, 10:49
SmittWesson, что значит комбинация сумм всех цифр в исходной строке? если это все возможные наборы чисел в заданной строке, то их 2^m, m - кол-во столбцов.
0
 Аватар для SmittWesson
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 12:21
Цитата Сообщение от SlavaSSU Посмотреть сообщение
если это все возможные наборы чисел в заданной строке, то их 2^m, m - кол-во столбцов.
Да-да. Точно. Спутал с полной перестановкой позиций цифр.
В таком случае, берём очередную цифру и прогоняем её через двоичное представление количества цифр в строке - 1 т.к. комбинация 0000 не имеет смысла.
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
12.11.2014, 12:48
SmittWesson, эту задачу можно решить быстрее, чем за n * 2^m.
0
Модератор
Эксперт по электронике
8962 / 6728 / 921
Регистрация: 14.02.2011
Сообщений: 23,752
12.11.2014, 12:58
Цитата Сообщение от -MaZaHaKa- Посмотреть сообщение
Есть любые числа, например:
1, 8, 4, 2
любые это разная позиция степеней двойки или вообще любые числа?
0
 Аватар для SmittWesson
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 12:59
Цитата Сообщение от SlavaSSU Посмотреть сообщение
эту задачу можно решить быстрее, чем за n * 2^m.
Вы сами себе противоречите. Не за n * 2^m, а за 2^m-1. Согласен, можно несколько ускорить, если в исходной строке имеются нули. Исключаем все двоичные комбинации совпадающие с суммированием нулей.
Например, для строки 5 0 6 0 исключить можно комбинации:0101, 0100, 0001 ну и само-собой - 0000.
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
12.11.2014, 13:02
SmittWesson, время работы(асимптотика) такого алгоритма(перебора) O(n * 2 ^ m), я говорю что эту задачу можно решить быстрее совсем другим способом.
0
 Аватар для SmittWesson
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 13:05
Цитата Сообщение от SlavaSSU Посмотреть сообщение
задачу можно решить быстрее совсем другим способом.
n - то откуда взялась? Строки добавляются по мере совпадения сумм чисел и вначале итераций не определены. Или Вы имеете в виду постоянную алгоритма?
А вот на счёт "другим способом", можно ли поподробней?
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
12.11.2014, 13:12
SmittWesson, нам надо каждое из N чисел представить в виде суммы M чисел. одно число мы можем представить в виде суммы M других за O(2 ^ m * m), ну и поэтому чтобы N чисел представить надо будет сделать N * 2 ^ M * M операций.

клик
0
 Аватар для SmittWesson
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 13:36
Цитата Сообщение от ValeryS Посмотреть сообщение
любые это разная позиция степеней двойки или вообще любые числа?
Любые вещественные числа. Просто, если числа не целые, их придётся округлять до предела точности иначе рзультат может быть неопределённым.
SlavaSSU согласен со статьёй в Вики. Спасибо за ссылочку.
0
Модератор
Эксперт по электронике
8962 / 6728 / 921
Регистрация: 14.02.2011
Сообщений: 23,752
12.11.2014, 14:15
Цитата Сообщение от SmittWesson Посмотреть сообщение
Любые вещественные числа.
тогда возможен вариант что число не представится суммой по количеству равной 1
например
1 3 7 9
тогда как представить число 2?
комбинация два раза 1?? т.е
2 0 0 0 ???
0
 Аватар для SmittWesson
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 17:03
Цитата Сообщение от ValeryS Посмотреть сообщение
тогда как представить число 2?
Комбинацией 0000. Т.к. чисел с такой суммой нет.
0
56 / 50 / 22
Регистрация: 17.03.2014
Сообщений: 143
12.11.2014, 17:52
допускает ли верхняя строка "1 8 4 2" повторяющиеся значения? скажем "1 1 4 2"
0
21 / 21 / 16
Регистрация: 30.09.2013
Сообщений: 262
14.11.2014, 21:36  [ТС]
SlavaSSU, SmittWesson, ValeryS, kaznachei67, Спасибо что откликнулись на моё сообщение. Таки нашел время зайти на форум и максимально внимательно ответить на каждое сообщение)

Цитата Сообщение от SlavaSSU Посмотреть сообщение
-MaZaHaKa-, сколько строк и столбцов будет максимум? И до скольки числа?
За неделю у меня было время подумать, и я пришел к выводу что здесь будет 10 строк железно и 4 столбца максимум (у всех курсовые имеют лишь 4 столбца). Также там могут быть отрицательные числа в строке.

Цитата Сообщение от SmittWesson Посмотреть сообщение
Просто, если числа не целые
Все числа будут целыми.

Цитата Сообщение от ValeryS Посмотреть сообщение
тогда возможен вариант что число не представится суммой по количеству равной 1
например
1 3 7 9
тогда как представить число 2?
комбинация два раза 1?? т.е
2 0 0 0 ???
Цитата Сообщение от kaznachei67 Посмотреть сообщение
допускает ли верхняя строка "1 8 4 2" повторяющиеся значения? скажем "1 1 4 2"
Думаю числа строки подобраны таким образом что бы данные ситуации не случались. По этому нужно будет вывести ошибку и прекратить программу.

Учитывая то что числа в принципе могут быть от -9 до 9 - то варианты различных комбинаций возрастает.


Спросил у преподавателя по программированию как можно реализовать такую систему, дал наводку на:
C++ Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (i = 0; i < 10; i++) {
    for (j = 0; j < 4; j++) {
        if (i == func(mas, j)) {
            mas[i][j] = 1;
        } else {
            mas[i][j] = 0;
        }
    }
}
 
int func(mas, j) {
    for (i = 0; i<j; i++) {
        a = mas[i]+a;
    }
 
    return a;
}
Как я вижу - она немного не завершенная. Она суммирует в прямом порядке:
1+8+4+2
8+4+2
4+2
2

Но не прыгает через значения
1+8+4
1+8+2
1+4+2
8+2
и тд.
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
14.11.2014, 22:05
Лучший ответ Сообщение было отмечено -MaZaHaKa- как решение

Решение

-MaZaHaKa-,

C++ (Qt) Скопировано
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
#include <iostream>
#include <cassert>
 
using namespace std;
 
const int N = 10, M = 4;
 
int a[N], b[M];
 
int main()
{
    int m;
    cout << "vvedite kolichestvo stolbcov" << endl;
    cin >> m;
    cout << "vvedite znacheniya v stolbcov" << endl;
    for(int i = 0; i < m; i++)
        cin >> b[i];
 
    int n;
    cout << "vvedite kolichestvo strok" << endl;
    cin >> n;
    cout << "vvedite znacheniya strok" << endl;
    for(int i = 0; i < n; i++)
        cin >> a[i];
 
    cout << "    ";
    for(int i = 0; i < m; i++)
        cout << b[i] << "  ";
    cout << endl;
    cout << endl;
 
    for(int i = 0; i < n; i++)
    {
        int need = a[i];
        bool ok = false;
        int ansmask = 0;
 
        for(int mask = 0; mask < (1 << m); mask++)
        {
            int sum = 0;
            for(int j = 0; j < m; j++)
                if(mask & (1 << j))
                    sum += b[j];
 
            if(sum == need)
            {
                ok = true;
                ansmask = mask;
                break;
            }
        }
 
        assert(ok);
 
        cout << a[i] << " = ";
        for(int j = 0; j < m; j++)
            if(ansmask & (1 << j))
                cout << "1  ";
            else
                cout << "0  ";
        cout << endl;
    }
 
    return 0;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.11.2014, 22:05
Помогаю со студенческими работами здесь

Перебор чисел
Здравствуйте. Допустим, есть у меня 2 числа (до 1000, например). Как мне перебрать все возможные комбинации произведений этих чисел? ...

перебор чисел и умножение
помогите плиз,делаю программу для вычисления уравнений с двумя неизвестными и мне надо перебирать числа по тысячным т.е. 0.001;0.002 и т....

Быстрый перебор восьмизначных чисел на С++
Доброго всем вечера, можете подсказать как с этим разобраться? Неободимо перебрать все числа от 1 до 12345678 и проверить что в каждом из...

Как сделать перебор чисел в массиве
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;random&gt; #include &lt;cstdlib&gt; #include &lt;ctime&gt; using namespace std; int main...

Перебор элементов массива
Добрый день, ув. форумчане. В наличии следующий код: int i; WCHAR *slovo = {L&quot;слово1&quot;, L&quot;слово2&quot;, ...,...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Новые блоги и статьи
Списки и кортежи в Python: различия, особенности, применение
py-thonny 13.04.2025
Python славится своей гибкостью при работе с данными. В арсенале языка есть две основные последовательные структуры данных, которые программисты используют ежедневно — списки и кортежи. Эти структуры. . .
Middleware в ASP.NET Core
UnmanagedCoder 13.04.2025
В ASP. NET Core термин "middleware" занимает особое место. Что же это такое? Middleware представляет собой программные компоненты, которые формируют конвейер обработки HTTP-запросов в приложении. . . .
Таблицы лута в Unity с MinMaxCurve и AnimationCurve
GameUnited 12.04.2025
Создание сбалансированного лута в играх — задача не из простых. Разработчики постоянно ищут способы настройки систем выпадения предметов, которые будут одновременно справедливыми для игроков и. . .
std::expected в C++: Управление ошибками
bytestream 12.04.2025
Обработка ошибок всегда была важной и одновременно сложной задачей в программировании на C++. На протяжении долгого времени разработчики использовали различные подходы: возвращаемые коды ошибок,. . .
Nullable типы и операторы объединения null в C#
UnmanagedCoder 12.04.2025
Многие шутят, что null — это миллиардная ошибка в программировании. И в этой шутке только доля шутки. Тони Хоар, создатель null-ссылки, сам назвал её своей "ошибкой на миллиард долларов". Почему?. . .
Аутентификация и авторизация JWT в микросервисах с API Gateway
stackOverflow 12.04.2025
В традиционных монолитных приложениях безопасность часто реализуется как единый защитный периметр - пользователь проходит аутентификацию один раз, после чего получает доступ ко всем функциям системы. . . .
TypeScript: Интерфейсы vs Типы
run.dev 11.04.2025
Современная разработка на JavaScript сталкивается с множеством проблем при масштабировании проектов. Типизация кода стала хорошим инструментом, помогающим избежать ошибок во время выполнения,. . .
Управление топиками и разделами Kafka
Javaican 11.04.2025
Apache Kafka — распределенная платформа потоковой передачи данных, которая стала стандартом для построения высоконагруженных систем обмена сообщениями. В современной архитектуре микросервисов,. . .
Миграция монолита в Event-Driven микросервисную архитектуру на C#
stackOverflow 11.04.2025
Монолитная архитектура – классический подход к разработке программного обеспечения. Это приложение, построенное как единое целое, где все компоненты тесно связаны между собой. Большинство проектов. . .
Go в Kubernetes: Управление ресурсами
golander 11.04.2025
Разработчики Go-приложений в Kubernetes часто сталкиваются с неожиданными проблемами производительности и даже внезапными отказами контейнеров. Причина этого кроется в особенностях взаимодействия. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер