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

06.05.2009, 15:39. **Показов** 2014. **Ответов** 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";
}

}

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ

Fraerrrrr

	Разбить N на более простые числа, в сумме дающие это N 06.05.2009, 15:39. Показов 2014. Ответов 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