С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
badgo
0 / 0 / 0
Регистрация: 16.01.2010
Сообщений: 33
#1

"Числовые группы" - C++

02.11.2010, 13:01. Просмотров 544. Ответов 6
Метки нет (Все метки)

"Числовые группы".
Два натуральных числа, больших 1, назовем "связанными", если одно получается из другого умножением на какое-то простое число. Например, числа 2 и 10 связаны,а 21 и 85 нет. Назовем совокупность натуральных чисел "группой", если для каждой пары чисел можно подобрать цепочку чисел, их связывающую, такую, что каждые два соседних числа в этой цепочке связаны. Например, совокупность (3,6,30,51) - группа, а (3,4,6,30) нет. Напишите программу,которая по введенному натуральному числу n(2<=n<=10^9) выдавала бы количество групп, на которые распадается отрезок натурального ряда от 2 до n.

Помогите решить задачу.Несколько раз прочитал условие, ничего толком не понял. Что такое связанные числа разобрался, а про группу ничего не понял.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2010, 13:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос "Числовые группы" (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

6
Day
1159 / 964 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
02.11.2010, 13:52 #2
Задача решается рекурсией.
Дано число N
Пусть p1, p2, ... - его разные простые делители
Тогда F(N) = F(N/p1) + F(N/p2) ...
F(n) - то самое количество групп

Добавлено через 5 минут
Извиняюсь.
Не все так просто.
Неправильно понял условие.
И не понял, почему (3,6,30,51) группа?
Как связать 30 и 51 ?
0
badgo
0 / 0 / 0
Регистрация: 16.01.2010
Сообщений: 33
02.11.2010, 13:55  [ТС] #3
Вот вот.
3 6 30 связанные,а 51 каким боком тут...
0
Day
1159 / 964 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
02.11.2010, 14:00 #4
И еще вопросик.
Совокупность состоящая из одного числа чвляется ли группой?
Вообще, видимо отрезок [2, N] можно разбить на группы разными способами.
Что нужно?
Найти все разбиения на группы ?
Какое-то одно ?
На Минимальное количество групп.
0
badgo
0 / 0 / 0
Регистрация: 16.01.2010
Сообщений: 33
02.11.2010, 14:28  [ТС] #5
Я привел полное условие задачи...
Сам ничего не понял,поэтому ответить не могу.
Завтра еще уточню правильность этого самого условия.
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
04.11.2010, 10:40 #6
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////
//Два натуральных числа, больших 1, назовем "связанными", если одно получается 
//из другого умножением на какое-то простое число. Например, числа 2 и 10 связаны,
//а 21 и 85 нет. Назовем совокупность натуральных чисел "группой", если для каждой 
//пары чисел можно подобрать цепочку чисел, их связывающую, такую, что каждые 
//два соседних числа в этой цепочке связаны. Например, совокупность (3,6,30,51) 
//- группа, а (3,4,6,30) нет. Напишите программу,которая по введенному натуральному 
//числу n(2<=n<=10^9) выдавала бы количество групп, на которые распадается отрезок 
//натурального ряда от 2 до n.
//////////////////////////////////////////////////////////////////////////////////////
const int N_MAX = 1000000000;
char  erat_sieve[N_MAX + 1] = {0};
//////////////////////////////////////////////////////////////////////////////////////
void  make_eratosthenes_sieve(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        erat_sieve[i] = 1;
    }    
    
    for(int p = 0; p <= n; )
    {
        do
        {            
            if(++p > n)
            {               
                return;
            }
 
        }while(erat_sieve[p] == 0);
 
        for(int i = 2; ; ++i)
        {
            if(n < p * i)
            {
                break;
            }
            else
            {
                erat_sieve[p * i] = 0;        
            }           
        }
    }    
}
//////////////////////////////////////////////////////////////////////////////////////
bool  is_prime_number(int k)
{
    return  erat_sieve[k] != 0;
}
//////////////////////////////////////////////////////////////////////////////////////
int  get_groups_count(int n)
{
    //Рассмотрим числовую группу, в которую входит простое число 2.
    //Очевидно, что мы можем включить в эту группу другое простое число p, 
    //если можем также включить туда и число (2 * p), так как два простых числа
    //могут быть связаны только через свое произведение. Но это возможно только
    //если 
    //  2 * p <= n.                                                       (1)
    //Отсюда следует, что в рассматриваемую группу входят все простые числа, 
    //удовлетворяющие условию (1), и все числа, являющиеся произведениями
    //всех их всевозможных наборов и принадлежащие отрезку, так как произведение
    // n простых чисел связано с произведением (n - 1) своих простых делителей через
    //любой свой простой делитель. Рассмотрим простое число q из отрезка, которое 
    //не удовлетворяет условию (1), т.е. для которого
    //  2 * q > n.                                                        (2)
    //Очевидно мы не можем включить к нему в группу ни одно число, так как 
    //из условия (2) следует, что любое связанное с ним число не принадлежит
    //нашему отрезку. Т.е. каждое простое число из отрезка, удовлетворяющее условию (2), 
    //образует отдельную группу. Отсюда следует, что для подсчета числа числовых 
    //групп на отрезке от 2 до n нужно подсчитать количество простых чисел 
    //на этом отезке, удовлетворяющих условию (2), и прибавить один.   
 
    int prime_count = 0;
    for(int i = n / 2 + 1; i <= n; ++i)
    {
        if(is_prime_number(i))
        {
            ++prime_count;
        }
    }
    return  ++prime_count;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));       
    int n = 0;
    const int N_MIN = 2;    
    do
    {
        std::cout << "Введите "
                  << N_MIN
                  << " <= n <= "
                  << N_MAX
                  <<": ";
        std::cin >> n;
    }while(n < 2);
 
    make_eratosthenes_sieve(n);
 
    std::cout << "Отрезок натурального ряда от 2 до "
              << n
              << std::endl
              << "распадается на "
              << get_groups_count(n)
              << " числовых групп."
              << std::endl;   
}
Добавлено через 5 часов 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
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////
//Два натуральных числа, больших 1, назовем "связанными", если одно получается 
//из другого умножением на какое-то простое число. Например, числа 2 и 10 связаны,
//а 21 и 85 нет. Назовем совокупность натуральных чисел "группой", если для каждой 
//пары чисел можно подобрать цепочку чисел, их связывающую, такую, что каждые 
//два соседних числа в этой цепочке связаны. Например, совокупность (3,6,30,51) 
//- группа, а (3,4,6,30) нет. Напишите программу,которая по введенному натуральному 
//числу n(2<=n<=10^9) выдавала бы количество групп, на которые распадается отрезок 
//натурального ряда от 2 до n.
//////////////////////////////////////////////////////////////////////////////////////
const int N_MAX = 1000000000;
char  erat_sieve[N_MAX + 1] = {0};
//////////////////////////////////////////////////////////////////////////////////////
void  make_eratosthenes_sieve(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        erat_sieve[i] = 1;
    }    
        
    for(int p = 0; p <= n; ++p)
    {
        if(erat_sieve[p] == 0) 
        {
            continue;
        }
 
        for(int i = 2; p * i <= n; ++i)
        {
            erat_sieve[p * i] = 0;
        }
    }    
}
//////////////////////////////////////////////////////////////////////////////////////
bool  is_prime_number(int k)
{
    return  erat_sieve[k] != 0;
}
//////////////////////////////////////////////////////////////////////////////////////
int  get_groups_count(int n)
{
    //Рассмотрим числовую группу, в которую входит простое число 2.
    //Очевидно, что мы можем включить в эту группу другое простое число p, 
    //если можем также включить туда и число (2 * p), так как два простых числа
    //могут быть связаны только через свое произведение. Но это возможно только
    //если 
    //  2 * p <= n.                                                       (1)
    //Отсюда следует, что в рассматриваемую группу входят все простые числа, 
    //удовлетворяющие условию (1), и все числа, являющиеся произведениями
    //всех их всевозможных наборов и принадлежащие отрезку, так как произведение
    // n простых чисел связано с произведением (n - 1) своих простых делителей через
    //любой свой простой делитель. Рассмотрим простое число q из отрезка, которое 
    //не удовлетворяет условию (1), т.е. для которого
    //  2 * q > n.                                                        (2)
    //Очевидно мы не можем включить к нему в группу ни одно число, так как 
    //из условия (2) следует, что любое связанное с ним число не принадлежит
    //нашему отрезку. Т.е. каждое простое число из отрезка, удовлетворяющее условию (2), 
    //образует отдельную группу. Отсюда следует, что для подсчета числа числовых 
    //групп на отрезке от 2 до n нужно подсчитать количество простых чисел 
    //на этом отезке, удовлетворяющих условию (2), и прибавить один.   
 
    int prime_count = 0;
    for(int i = n / 2 + 1; i <= n; ++i)
    {
        if(is_prime_number(i))
        {
            ++prime_count;
        }
    }
    return  ++prime_count;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));       
    int n = 0;
    const int N_MIN = 2;    
    do
    {
        std::cout << "Введите "
                  << N_MIN
                  << " <= n <= "
                  << N_MAX
                  <<": ";
        std::cin >> n;
    }while(n < 2);
 
    make_eratosthenes_sieve(n);
 
    std::cout << "Отрезок натурального ряда от 2 до "
              << n
              << std::endl
              << "распадается на "
              << get_groups_count(n)
              << " числовых групп."
              << std::endl;   
}
2
Day
1159 / 964 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
15.11.2010, 13:38 #7
badgo, А мне вдруг показалось все очень простым.
Наверное, ищется все-таки минимальное количество групп, т.к. максимальное = n-1 (каждое число образует группу).
Все числа до n/2 и все составные <= n образуют одну большую группу. (от любого до любого можно добраться через умножение и деление на простое, не вылезая за n)
Например, ежели простые p, q < n/2 , то есть цепочка: p - 2*p - 2 - 2*q - q.
А ежели они не простые, добираемся до любого простого множителя, а уж они-то связаны (т.к. <n/2). То же самое с составными >n/2.
А вот простые >n/2 остаются в одиночестве, т.е. каждое из них образует одноэлементную группу.
Остается только подсчитать кол-во простых от n/2 до n
и прибавить 1.

Добавлено через 22 минуты
Вот ведь как бывает, вышел на балкон покурить, чего-то вспомнил твою задачу, и с 13-го этажа она - как на ладони.
Mr.X конечно, совершенно прав.
1
15.11.2010, 13:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2010, 13:38
Привет! Вот еще темы с ответами:

Реализовать структуру "Анкета" с полями "Фамилия", "Пол" и "Адрес" - C++
Здравствуйте. Проходим тему Структуры, не могу понять, как определить количество, само задание: #include &lt;iostream&gt; #include...

Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" - C++
Функция - расчёт зарплаты по нагрузке и оплате часа для определенной категории. Категория Оплата часа Вторая 150 Первая 200 ...

Создать иерархию классов "Фирма", "Бухгалтер", "Сотрудник", "Зарплата" - C++
Само по себе понятие &quot;зарплата&quot; не особенно конкретное: оно включает и почасовую, и ставочную зарплату, и комиссионные, и процент с продаж....

по строкам.замените в слове сочетание "му" на "а" , а букву "ы" на "ца". очень нужно - C++
замените в слове сочетание &quot;му&quot; на &quot;а&quot; , а букву &quot;ы&quot; на &quot;ца&quot;. очень нужно Добавлено через 21 час 4 минуты неужели никто не знает...


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

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

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