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

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

12.11.2014, 00:23. Показов 4280. Ответов 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,2,3,9,4,5,6,9,7,8,0}, тут...

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

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

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

клик
0
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 13:36 12
Цитата Сообщение от ValeryS Посмотреть сообщение
любые это разная позиция степеней двойки или вообще любые числа?
Любые вещественные числа. Просто, если числа не целые, их придётся округлять до предела точности иначе рзультат может быть неопределённым.
SlavaSSU согласен со статьёй в Вики. Спасибо за ссылочку.
0
Модератор
Эксперт по электронике
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,716
12.11.2014, 14:15 13
Цитата Сообщение от SmittWesson Посмотреть сообщение
Любые вещественные числа.
тогда возможен вариант что число не представится суммой по количеству равной 1
например
1 3 7 9
тогда как представить число 2?
комбинация два раза 1?? т.е
2 0 0 0 ???
0
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
12.11.2014, 17:03 14
Цитата Сообщение от ValeryS Посмотреть сообщение
тогда как представить число 2?
Комбинацией 0000. Т.к. чисел с такой суммой нет.
0
56 / 50 / 22
Регистрация: 17.03.2014
Сообщений: 143
12.11.2014, 17:52 15
допускает ли верхняя строка "1 8 4 2" повторяющиеся значения? скажем "1 1 4 2"
0
21 / 21 / 16
Регистрация: 30.09.2013
Сообщений: 262
14.11.2014, 21:36  [ТС] 16
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 17
Лучший ответ Сообщение было отмечено -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
14.11.2014, 22:05
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.11.2014, 22:05
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Новые блоги и статьи
Какой язык программировани­я лучший для разработки нейронных сетей
InfoMaster 20.01.2025
В современном мире технологий искусственные нейронные сети становятся неотъемлемой частью множества инновационных решений, от распознавания речи до автоматического управления транспортными. . .
Как подключить JavaScript файл в другом JavaScript файле
InfoMaster 20.01.2025
В современной веб-разработке организация кодовой базы играет ключевую роль в создании масштабируемых и поддерживаемых приложений. Модульность и правильное структурирование кода стали неотъемлемыми. . .
Как откатить изменения в исходниках, не внесенные в Git
InfoMaster 20.01.2025
При работе с системой контроля версий Git разработчики часто сталкиваются с необходимостью отменить внесенные изменения в исходном коде. Особенно актуальной становится ситуация, когда изменения еще. . .
В чем разница между px, in, mm, pt, dip, dp, sp
InfoMaster 20.01.2025
В мире цифрового дизайна и разработки интерфейсов правильный выбор единиц измерения играет ключевую роль в создании качественного пользовательского опыта. История развития систем измерений для. . .
Как изменить адрес удалённого репозитория (origin) в Git
InfoMaster 20.01.2025
В терминологии Git термин origin является стандартным именем для основного удаленного репозитория, с которым взаимодействует локальная копия проекта. Когда разработчик клонирует репозиторий с. . .
Как переместить последние коммиты в новую ветку (branch) в Git
InfoMaster 20.01.2025
При работе над проектом часто возникают ситуации, когда необходимо изолировать определенные изменения от основной линии разработки. Это может быть связано с экспериментальными функциями, исправлением. . .
Как вернуть результат из асинхронной функции в JavaScript
InfoMaster 20.01.2025
Асинхронное программирование представляет собой фундаментальную концепцию в JavaScript, которая позволяет выполнять длительные операции без блокировки основного потока выполнения программы. В. . .
Какой локальный веб-сервер выбрать
InfoMaster 19.01.2025
В современной веб-разработке локальные веб-серверы играют ключевую роль, предоставляя разработчикам надежную среду для создания, тестирования и отладки веб-приложений без необходимости использования. . .
Почему планшеты и iPad уже не так популярны, как раньше
InfoMaster 19.01.2025
Эра революционных инноваций История планшетов началась задолго до того, как эти устройства стали привычными спутниками нашей повседневной жизни. В начале 1990-х годов появились первые прототипы,. . .
Как самому прошить BIOS ноутбука
InfoMaster 19.01.2025
BIOS (Basic Input/ Output System) представляет собой важнейший компонент любого компьютера или ноутбука, который обеспечивает базовое взаимодействие между аппаратным и программным обеспечением. . .
Какой Linux выбрать для домашнего компьютера
InfoMaster 19.01.2025
Современные реалии выбора операционной системы В современном мире выбор операционной системы для домашнего компьютера становится все более важным решением, которое может существенно повлиять на. . .
Как объединить два словаря одним выражением в Python
InfoMaster 19.01.2025
В мире программирования на Python работа со словарями является неотъемлемой частью разработки. Словари представляют собой мощный инструмент для хранения и обработки данных в формате "ключ-значение". . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru