Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
QAQA
0 / 0 / 1
Регистрация: 15.03.2014
Сообщений: 42
#1

Разбить число N на K элементов (не меньше, не больше) и записать так, чтобы множество не повторялось - C++

08.09.2014, 23:10. Просмотров 631. Ответов 8
Метки нет (Все метки)

Здравствуйте, задача вот в чем: требуется разбить число N на K элементов (не меньше, не больше) и записать так, чтобы множество не повторялось.
Пример: N=10, K=4
{1,1,1,7}
{1,1,2,6}
http://www.cyberforum.ru/cpp-beginners/thread1879555.html
{1,1,3,5}
{1,1,4,4}
{1,2,2,5}
{1,2,3,4}
{1,3,3,3}
{2,2,2,4}
{2,2,3,3}

Видел много задач для конкретного K, но универсального решения - нет.
Думал, записывать в одномерный массив A, с последующим его очищением (но туплю с циклами).
Пишу в C++ Builder'е, вот такой "копипаст" с гугла (неправильный вывод в Memo1, но прошу это не учитывать).

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
int K,R[5],S[5],d,l,N,sum;
Memo1->Clear();
N=StrToInt(Edit1->Text);
//K=StrToInt(Edit2->Text);
//start
S[0]=N; R[0]=1 ;d=1;
 
    while (S[0]>1)      {
        sum=0;
        if (S[d]=1) {
            sum=sum+R[d]; 
            d=d-1;
                    }
            sum=sum+S[d];
            R[d]=R[d]-1;
            l=S[d]-1;
        if (R[d]>0) {
            d=d+1;  }
            S[d]=l;
            R[d]=sum/l;
            l=sum % l;
        if (l!=0) {
            d=d+1;
            S[d]=l;
            R[d]=1;
        }
                        }
Memo1->Lines->Add(IntToStr(S[3])); //вывод
Как лучше? Мне бы алгоритм, блок-схему, а то интеллекта не хватает.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2014, 23:10
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Разбить число N на K элементов (не меньше, не больше) и записать так, чтобы множество не повторялось (C++):

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

Число элементов массива, не больше максимального, но и не меньше минимального
Число элементов массива Х,которые не превосходят максимального элемента масива...

Вычислить Среднее арифм. значение элементов массива и число пар элементов которых сосед слева (т.е. индекс которого на 1 меньше) больше по величине
Разработать функцию, обрабатывающую массив и вычисляющую две величины. Кроме...

Вывести на экран m первых элементов последовательности так, чтобы их сумма оказалась меньше 1000
Вывести на экран m первых (a1, a2, …) элементов последовательности an=2+2n²,...

Напечать число, которое меньше максимального элемента,но больше всех остальных элементов
Составить программу,которая в массиве A находит второе по величине...

8
S_el
2133 / 1661 / 354
Регистрация: 15.12.2013
Сообщений: 6,593
08.09.2014, 23:29 #2
Цитата Сообщение от QAQA Посмотреть сообщение
Как лучше? Мне бы алгоритм, блок-схему, а то интеллекта не хватает.
Не интеллекта, а опыта и возможно силы воли.

Цитата Сообщение от QAQA Посмотреть сообщение
Здравствуйте, задача вот в чем: требуется разбить число N на K элементов (не меньше, не больше) и записать так, чтобы множество не повторялось.
Задача не ясна.Попробую переформулировать:
Определить множество наборов разбиения числа N на K слагаемых.

Добавлено через 7 минут
Добавлю поправку к формулировке:
с группировкой слагаемых по возрастанию.
0
QAQA
0 / 0 / 1
Регистрация: 15.03.2014
Сообщений: 42
08.09.2014, 23:41  [ТС] #3
Цитата Сообщение от S_el Посмотреть сообщение
Определить множество наборов разбиения числа N на K слагаемых.
Да, именно так.
Но,всё-таки, как лучше делать, если N и K не задаются сразу - их надо вводить?

Или же:

Говорят, что число n разбит на k составляющих b[1],...,B[k], если:
*B[1]+...+B[k]=N
где k, B[1],...+B[K]>0. Сумы считаются эквивалентными, если они отличаются только порядком слагаемых. Слагаемые называют также компонентами разбиения числа n.
Пусть требуется найти все возможные разбиения числа n на слагаемые. Данная задача методологически связана с задачей разбиения на множествах.
Генерирование разбиения числа. Разбиение числа n на k компонент можно продолжать в растущем лексикографическом порядке, начиная с разбивки, в котором B[1]=1, B[2]=2,..., B[i-1]=N-K+1
и продолжая процесс следующим образом.
Для получения следующего разбиения по данному Просматриваем элементы данного разбиения в порядке справа налево, находя самые правые компонента bi такую​​, что B[1]-B[K]>=2. Далее заменяем все компоненты
B[j](j=i,k-1) на значение B[i]+1.

Но у меня никак не получается отобразить всё это в циклах и т.д.!
0
S_el
2133 / 1661 / 354
Регистрация: 15.12.2013
Сообщений: 6,593
08.09.2014, 23:51 #4
Цитата Сообщение от QAQA Посмотреть сообщение
Но у меня никак не получается отобразить всё это в циклах и т.д.!
Я могу предложить 3 варианта:
1. Обратится в раздел по алгоритмам,там люди более опытные в таких вопросах и подскажут быстрее.
2.Подождать пока кто-то не выложит свою реализацию.
3.Начинать реализовывать самому с подсказками форумчан ,двигаясь от частного решения к общему.В последствии прогнать на разных "частных случаях и доработать".

В общем я начну 1-ый шаг,вы его программируете и выкладываете.Далее мы его "чистим" и переходим к обсуждению следующего шага.Затем вы его реализовываете и так далее пока не решим задачу,не опустим руки или не получим готовое решение.
Хотя полезнее сделать самому,пускай и с подсказками.

Проверить N и K,если второе больше первого return false или cerr<<"Операция невозможна";
или исключение,ну в общем как больше нравится.
Проверить на равенство => определить набор из единиц в случае успеха.
Самый неприятный вариант K все-таки меньше N.
Со структурой данных,где все это будет хранится разберемся позднее,начнем со стандартного массива,размером K.
Выделить строку из K-1 единиц и N-K+1.
Будем последовательно уменьшать последний элемент,пока он не станет равным предпоследнему,или он увеличенный на единицу станет больше уменьшенного на 1 предпоследнего.

P.S. Сам в алгоритмах не силен,а в теории чисел и множеств крайне слаб.
0
_Ivana
3232 / 1860 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
09.09.2014, 00:12 #5
Мои мысли - проще написать рекурсию. Взяли единицу, осталась девятка, пошли в рекурсию с ней, взяли снова единицу - осталась восьмерка и так далее, глубина рекурсии строго 4, последний раз берем остаток, сколько "взяли" инкрементируется в цикле рекурсии. Хранить результат можно вообще не надо, сразу выводить на печать и все. На С думаю написать не будет сложностей.

А теперь не мои мысли Мне очень интересно сейчас делать такие простые задачки на языке, в котором очень хочу разобраться. Хотел сам написать, но ума пока не хватает... Вот здесь http://www.cyberforum.ru/haskell/thread1042665.html приведен код для подобного, у меня работает, но понять его и будет моей задачей на этот вечер
0
S_el
2133 / 1661 / 354
Регистрация: 15.12.2013
Сообщений: 6,593
09.09.2014, 00:35 #6
Цитата Сообщение от _Ivana Посмотреть сообщение
Мне очень интересно сейчас делать такие простые задачки на языке, в котором очень хочу разобраться. Хотел сам написать, но ума пока не хватает...
Эхх,а могли бы присоеденится и написать вместе.Написал ТС,отвечу и вам,тут не в уме дело.

Цитата Сообщение от _Ivana Посмотреть сообщение
Мои мысли - проще написать рекурсию. Взяли единицу, осталась девятка, пошли в рекурсию с ней, взяли снова единицу - осталась восьмерка и так далее, глубина рекурсии строго 4, последний раз берем остаток, сколько "взяли" инкрементируется в цикле рекурсии.
Я тоже думал о рекурсивном варианте,но условие о упорядоченности заставили меня от него отказаться.Надо будет мне чем-то функциональным заняться,там много чего на рекурсивной обработке сделано.

Добавлено через 8 минут
Цитата Сообщение от _Ivana Посмотреть сообщение
приведен код для подобного, у меня работает, но понять его и будет моей задачей на этот вечер
Не посмотрел когда отвечал на код,теперь дополню.
Там задача немного другая,здесь есть дополнительные ограничения + язык другой.
Так что,присоединяйтесь
0
_Ivana
3232 / 1860 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
09.09.2014, 01:29 #7
А присоединюсь Только на С мне непривычно консольные проекты создавать, а в оконные долго разбираться как строки выводить, поэтому держите на том, что быстро и удобно Только базовые типы, легко переносится на С, логика проста как палка-веревка:
1C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Перем КоличествоСлагаемых;
//---------------------------------------------------------------------------------------------
 
Процедура Разложить(Знач Остаток, Знач Результат = "", Знач Уровень = 1, Знач ПоследнееСлагаемое = 1)
    Если Уровень = КоличествоСлагаемых Тогда
        Сообщить(Результат + "," + Остаток);
    Иначе
        Для й = ПоследнееСлагаемое По Остаток/2 Цикл
            Разложить(Остаток - й, Результат + ?(Уровень = 1, "", ",") + й, Уровень + 1, й)
        КонецЦикла;
    КонецЕсли;
КонецПроцедуры
//---------------------------------------------------------------------------------------------
 
Процедура Сформировать()
    КоличествоСлагаемых = 4;
    ОчиститьОкноСообщений();
    Разложить(10);
КонецПроцедуры
//---------------------------------------------------------------------------------------------
ЗЫ подсветка синтаксиса конечно страшная, но так местный движок 1С-код подсвечивает
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
09.09.2014, 01:40 #8
QAQA,
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
#include <iostream>
 
using namespace std;
 
int ans[11];
int n, k;
 
void rec(int sum, int pos)
{
    int last = (pos == 0 ? 1 : ans[pos - 1]);
 
    if(sum < (k - pos) * last)
        return;
 
    if(pos == k)
    {
        if(sum == 0)
        {
            for(int i = 0; i < k; i++)
                cout << ans[i] << ' ';
            cout << '\n';
        }
 
        return;
    }
 
    for(int next = last; next <= n; next++)
    {
        ans[pos] = next;
        rec(sum - next, pos + 1);
    }
}
 
int main()
{
    cin >> n >> k;
    rec(n, 0);
    return 0;
}
1
_Ivana
3232 / 1860 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
09.09.2014, 01:48 #9
Во-во, почти дословный перевод на английский Только имхо у меня пооптимальнее сделан верхний предел цикла, и от этого не приходится делать лишний заход и пустые возвраты когда следующее слагаемое меньше предыдущего.
0
09.09.2014, 01:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.09.2014, 01:48
Привет! Вот еще темы с решениями:

Вектор классов. Число конструкторов элементов меньше числа деструкторов. Как так ?
Добрый день. Разбираюсь с stl с++11 в частности с векторами. Имеем простейший...

Задан массив целых чисел и целое число k. Определить, сколько элементов меньше k, равны k и больше k
Задан массив целых чисел и целое число k. Определить, сколько элементов меньше...

Вывести на печать число, которое меньше максимального элемента массива, но больше всех других элементов
Составить программу, которая в массиве A находит второе по величине число...


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

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

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