Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Fraerrrrr
Сообщений: n/a
#1

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

06.05.2009, 15:39. Просмотров 1069. Ответов 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
Низкий поклон тому, кто сможет воплотить это задание в жизнь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2009, 15:39     Разбить N на более простые числа, в сумме дающие это N
Посмотрите здесь:

Простые числа, или как это работает? - C++
Доброго времени суток всем участникам этого форума =) У меня как у начинающего программиста возникла затрудняющая ситуация, есть готовый...

Если к сумме цифр двузначного числа прибавить квадрат этой суммы, то снова получится это двузначное число - C++
Задание: Написал примерный код, но сомневаюсь что правильно применил цикл. Сейчас компилятора нету проверить не могу. Посмотрите и...

Найти все простые числа из интервала (1000, 9999), у которых сумма первой и второй цифры равна сумме третьей и четвертой цифры. - C++ Builder
Всем привет! :beach: Дали 6 заданий по практике, нужно выбрать одну из них и написать на С++ (Builder) и Pascal ABC. Я пробовал зделать...

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа - C++
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа. Простые числа это когда они делятся только...

Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б - C++
#include <stdio.h> #include <iostream> #include <conio.h> #include <math.h> using std::cout; using std::cin; using...

Выведите все числа на отрезке от a до b, дающие остаток c при делении на d - C++
1.Даны натуральное n, m. Получить сумму m последних цифр числа n. 2.Вводятся 4 числа: a, b, c и d. Выведите все числа на отрезке от a до...

Разбить число на множители и определить простые они или нет - C++
Нужна помощь народ! Надо написать код чтобы работал по такому принципу: разбить число на множители и определить простые они или нет, если...

Разбить целое число на простые множители с помощью рекурсивного алгоритма - C++
Мне нужно разбить целое число на простые множители, этот алгоритм должен быть обязательно рекурсивным.. Помогите пожалуйста.

Разбить файл на строки длиной не более 60 символов - C++
Проблема в том, что функция, работает не корректно... А вот понять в чем проблема я чет не могу... (Хотя есть ощущение, что функция...

Существуют натуральные числа равные сумме кубов своих цифр. Найдите такие числа в заданном интервале - C++
Существуют натуральные числа равные сумме кубов своих цифр ,например 370 ,33+73+03=370. Найдите такие числа в интервале от «а» до «b».


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.05.2009, 20:44     Разбить N на более простые числа, в сумме дающие это N #2
не понял,а при чем тут НОК?

Добавлено через 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;
}
Fraerrrrr
Сообщений: n/a
07.05.2009, 04:07     Разбить N на более простые числа, в сумме дающие это N #3
Цитата Сообщение от 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
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
07.05.2009, 10:05     Разбить N на более простые числа, в сумме дающие это N #4
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
0 / 0 / 0
Регистрация: 30.01.2014
Сообщений: 3
30.01.2014, 00:27     Разбить N на более простые числа, в сумме дающие это N #5
#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";
}


}
Yandex
Объявления
30.01.2014, 00:27     Разбить N на более простые числа, в сумме дающие это N
Ответ Создать тему
Опции темы

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