Разбить N на более простые числа, в сумме дающие это N

06.05.2009, 15:39. **Показов** 1980. **Ответов** 4

Студворк — интернет-сервис помощи студентам

Нашел я как-то в одной книге задачу. До сих пор бьюсь над ее решением. Может кто подскажет программу для ее решения (на Visual C++,либо на VBA либо на Паскале))). Вот текст задачи (на первый взгляд, ничего схожего с программированием):

Парламент состоит из N делегатов. Делегаты должны разделиться на группы (фракции); кол-во депутатов в каждой группе должно отличаться от кол-ва депутатов в любой другой группе. Каждый день каждая фракция посылает одного представителя в некий президиум. Парламент начинает работать в том случае, когда состав президиума отличен от составов президиумов предыдущих дней.
Составить программу, которая бы определяла оптимальное число фракций и кол-во делегатов в каждой из них так, чтобы парламент мог работать как можно дольше. Рассчитанные значения кол-ва делегатов в каждой фракции, сортированные по возрастанию, вывести в выходном текстовом файле.

Короче говоря, нужно разбить N на более простые числа, в сумме дающие это N. Причем начинать надо с двух элементов, рассмотрев все возможные варианты (например, если N=9, то: а=2, b=7 или a=3, b=6, или a=4, b=5). В каждом случае надо найти их наименьшее общее кратное (т.е. НОК(2,7)=14, НОК(3,6)=6, НОК(4,5)=20) и выбрать наибольшее. Точно такую-же операцию надо выполнить для трех элементов, четырех и т.д. В результате должна получиться комбинация чисел в сумме дающее N и имеющее наибольшее наименьшее общее кратное(!простите за тавтологию!). Вот два примера:
N=7: 3 4
N=31: 2 3 5 6 7 8
Низкий поклон тому, кто сможет воплотить это задание в жизнь.

@Humanitis · 06.05.2009, 20:44

не понял,а при чем тут НОК?

Добавлено через 2 часа 35 минут 45 секунд

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
#include <iostream>
#include <vector>
 
class CorrectGroups
{};
class AccGroups
{};
 
template <typename _It,typename _Ty>
    inline _Ty CalculGroups(_It _Rhs,const _Ty _N,AccGroups)
    {
        _Ty _Val=_N;
        _Ty _Count=2;
        while(_Count<=_Val)
        {
            *_Rhs++=_Count;
            _Val-=_Count++;
        }
        return _Val;
    }
 
template <typename _It,typename _Ty>
    inline _Ty CalculGroups(_It _Rhs,const _Ty _N,CorrectGroups)
    {
        _Ty _Val=_N;
        while(_Val--)
            ++*_Rhs++;
        return _Val;
    }
 
int main()
{
    const int N=31;
    std::vector<int> vGroups;
    CalculGroups(vGroups.rbegin(),CalculGroups(std::back_inserter(vGroups),N,AccGroups()),CorrectGroups());
    std::copy(vGroups.begin(),vGroups.end(),std::ostream_iterator<int>(std::cout," "));
    return 0;
}

07.05.2009, 04:07

Сообщение от Humanitis

не понял,а при чем тут НОК?

Добавлено через 2 часа 35 минут 45 секунд

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
#include <iostream>
#include <vector>
 
class CorrectGroups
{};
class AccGroups
{};
 
template <typename _It,typename _Ty>
    inline _Ty CalculGroups(_It _Rhs,const _Ty _N,AccGroups)
    {
        _Ty _Val=_N;
        _Ty _Count=2;
        while(_Count<=_Val)
        {
            *_Rhs++=_Count;
            _Val-=_Count++;
        }
        return _Val;
    }
 
template <typename _It,typename _Ty>
    inline _Ty CalculGroups(_It _Rhs,const _Ty _N,CorrectGroups)
    {
        _Ty _Val=_N;
        while(_Val--)
            ++*_Rhs++;
        return _Val;
    }
 
int main()
{
    const int N=31;
    std::vector<int> vGroups;
    CalculGroups(vGroups.rbegin(),CalculGroups(std::back_inserter(vGroups),N,AccGroups()),CorrectGroups());
    std::copy(vGroups.begin(),vGroups.end(),std::ostream_iterator<int>(std::cout," "));
    return 0;
}

Это весь код программы?))))я не знаю толком C++,можно с комментариями?в осноном работаю на Vba,Maple....

@Humanitis · 07.05.2009, 10:05

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
#include <iostream>
#include <vector>
 
class CorrectGroups
{};
class AccGroups
{};
 
template <typename _It,typename _Ty>
    inline _Ty CalculGroups(_It _Rhs,const _Ty _N,AccGroups)
    {
//создаем группы,в первой группе 2 делегата,в каждой следующей на 1 больше
//цикл продолжаем пока достаточно делегатов,чтоб создать новую группу 
        _Ty _Val=_N;
        _Ty _Count=2;
        while(_Count<=_Val)
        {
            *_Rhs++=_Count;
            _Val-=_Count++;
        }
        return _Val;
    }
 
template <typename _It,typename _Ty>
    inline _Ty CalculGroups(_It _Rhs,const _Ty _N,CorrectGroups)
    {
//корректируем группы оставшимися делегатами
//добавляем в каждую группу по одному делегату,начиная с самой многочисленной  
//до тех пор пока есть свободные делегаты
        _Ty _Val=_N;
        while(_Val--)
            ++*_Rhs++;
        return _Val;
    }
 
int main()
{
    const int N=31;
    std::vector<int> vGroups;//вектор групп
//считаем колличество делегатов в группах    CalculGroups(vGroups.rbegin(),CalculGroups(std::back_inserter(vGroups),N,AccGroups()),CorrectGroups());
//вывод всех групп через пробел в стандартный поток 
    std::copy(vGroups.begin(),vGroups.end(),std::ostream_iterator<int>(std::cout," "));
    return 0;
}

@RinKaganime · 30.01.2014, 00:27

#include "iostream"
#include "conio.h"
#include < ctime >
#include < iomanip >
#include <windows.h>
#include <math.h>
using namespace std;
int z;
void prost(int a, int b)
{
bool q=a%b;
if((a%b)&&(b<sqrt(a)+2))
{
++b;
z=b;
prost(a,b);
}
}
bool fi1(int i)
{
z=0;
prost(i, 2);
if(z>sqrt(i)+1)
return 1;
else
return 0;

}

bool fi2(int a)
{
int fPare, sPare;
fPare=a%10;
a/=10;
fPare+=a%10;
a/=10;
sPare=a%10;
a/=10;
sPare+=a%10;
if(fPare==sPare)
return 1;
else
return 0;
}

int main()
{
setlocale(LC_ALL, "");
srand(time(NULL));

int m1[8999]={0};
for(int i=1000; i<10000; ++i)
{
if(filter1(i))
if(filter2(i))
cout<<i<<"\t";
}

}

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

Fraerrrrr

	Разбить N на более простые числа, в сумме дающие это N 06.05.2009, 15:39. Показов 1980. Ответов 4 Метки нет (Все метки) Нашел я как-то в одной книге задачу. До сих пор бьюсь над ее решением. Может кто подскажет программу для ее решения (на Visual C++,либо на VBA либо на Паскале))). Вот текст задачи (на первый взгляд, ничего схожего с программированием): Парламент состоит из N делегатов. Делегаты должны разделиться на группы (фракции); кол-во депутатов в каждой группе должно отличаться от кол-ва депутатов в любой другой группе. Каждый день каждая фракция посылает одного представителя в некий президиум. Парламент начинает работать в том случае, когда состав президиума отличен от составов президиумов предыдущих дней. Составить программу, которая бы определяла оптимальное число фракций и кол-во делегатов в каждой из них так, чтобы парламент мог работать как можно дольше. Рассчитанные значения кол-ва делегатов в каждой фракции, сортированные по возрастанию, вывести в выходном текстовом файле. Короче говоря, нужно разбить N на более простые числа, в сумме дающие это N. Причем начинать надо с двух элементов, рассмотрев все возможные варианты (например, если N=9, то: а=2, b=7 или a=3, b=6, или a=4, b=5). В каждом случае надо найти их наименьшее общее кратное (т.е. НОК(2,7)=14, НОК(3,6)=6, НОК(4,5)=20) и выбрать наибольшее. Точно такую-же операцию надо выполнить для трех элементов, четырех и т.д. В результате должна получиться комбинация чисел в сумме дающее N и имеющее наибольшее наименьшее общее кратное(!простите за тавтологию!). Вот два примера: N=7: 3 4 N=31: 2 3 5 6 7 8 Низкий поклон тому, кто сможет воплотить это задание в жизнь.

@RinKaganime 0 / 0 / 0 Регистрация: 30.01.2014 Сообщений: 3
	30.01.2014, 00:27
	#include "iostream" #include "conio.h" #include < ctime > #include < iomanip > #include <windows.h> #include <math.h> using namespace std; int z; void prost(int a, int b) { bool q=a%b; if((a%b)&&(b<sqrt(a)+2)) { ++b; z=b; prost(a,b); } } bool fi1(int i) { z=0; prost(i, 2); if(z>sqrt(i)+1) return 1; else return 0; } bool fi2(int a) { int fPare, sPare; fPare=a%10; a/=10; fPare+=a%10; a/=10; sPare=a%10; a/=10; sPare+=a%10; if(fPare==sPare) return 1; else return 0; } int main() { setlocale(LC_ALL, ""); srand(time(NULL)); int m1[8999]={0}; for(int i=1000; i<10000; ++i) { if(filter1(i)) if(filter2(i)) cout<<i<<"\t"; } } 0