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

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

Войти
Регистрация
Восстановить пароль
 
Лемур
0 / 0 / 0
Регистрация: 09.12.2009
Сообщений: 14
#1

найти в массиве наибольшее подмножество... - C++

09.12.2009, 19:08. Просмотров 589. Ответов 6
Метки нет (Все метки)

задача:
Найти в массиве натуральных чисел самое большое подмножество элементов в котором любые два числа взаимнопросты

помогите пожалуйста...ну никак не получается. заранее спасибо
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2009, 19:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос найти в массиве наибольшее подмножество... (C++):

Найти наибольшее из чисел в массиве - C++
Дано n действительных чисел: x1, x2,...,xn. Найти наибольшее среди них.

Найти наибольшее значение курса доллара в массиве - C++
Помогите решить задачу. Курс доллара в течение года менялся в диапазоне от 28руб. до 30руб. Найти наибольшее значение курса доллара. В...

Как в динамическом массиве найти наибольшее значение? - C++
Как в динамическом массиве найти наибольшее значение? srand(time(NULL)); int n = 0; cin >> n; while(i=max) int **a = new int* ; ...

Найти в массиве наибольшее число подряд идущих одинаковых элементов - C++
#include<stdio.h> #include<stdlib.h> #include <iostream> #include<conio.h> #include<math.h> //#define size 10 using namespace...

Найти в массиве наибольшее число подряд идущих одина*ковых элементов. - C++
Народ надо решить задачку...на простом СИ! Кто поможет буду благодарен... Найти в массиве наибольшее число подряд идущих одина*ковых...

Исключить из двух массивов одинаковые значения, и найти в первом массиве наибольшее - C++
Помогите!!! Написать код который будет запрашивать ввести пользователя два массива. Исключить из двух массивов одинаковые значения, и найти...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2009, 12:40 #2
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
#include<iostream.h>
#include<windows.h>
bool prov_prost(int a, int b)
{
    int temp;
    if(a>b)
    { 
        temp=a;
        a=b;
        b=temp;
    }
    if(a==b)
        return false;
    for(temp=2; temp<=a; temp++)
        if(a%temp==0 && b%temp==0)
            return false;
    return true;
}   
int main()
{   
    int i, j, n, *temp, *mas, *itog, count_itog=1;
    bool fl=true, fl1;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå Г°Г*çìåð Г¬Г*Г±Г±ГЁГўГ* Г*Г*ГІГіГ°Г*ëüГ*ûõ Г·ГЁГ±ГҐГ« :";
    cin>>n;
    temp=new int[n];
    mas=new int[n];
    itog=new int[n];
    cout<<"Ââåäèòå Г·ГЁГ±Г«Г* Г¬Г*Г±Г±ГЁГўГ*"<<endl;
    for(i=0; i<n; i++)
    {
        cin>>mas[i];
        temp[i]=1;
        itog[i]=0;
 
    }
    itog[0]=1;
    while(fl)
    {
        fl=false;
        for(i=0;!fl && i<n; i++)
            if(temp[i]==1)
                fl=true;
        fl1=true;
        for(i=0; fl1 && i<n-1; i++)
            for(j=i+1; fl1 && j<n; j++)
                if(temp[i]!=0 && temp[j]!=0)
                    fl1=prov_prost(mas[i], mas[j]);
        if(fl1)
        {
            j=0;
            for(i=0; i<n; i++)
                if(temp[i]!=0)
                    j++;
            if(j>count_itog)
            {
                for(i=0; i<n; i++)
                    itog[i]=temp[i];
                count_itog=j;
            }
        }
        temp[0]--;
        for(i=0; i<n; i++)
            if(temp[i]<0)
            {
                temp[i]=1;
                temp[i+1]--;
            }
    }
    for(i=0; i<n; i++)
        if(itog[i]!=0)
            cout<<mas[i]<<" ";
    cout<<endl;
 
    return 0;
}
Можно и проще, но сегодня голова тяжелая
1
Лемур
0 / 0 / 0
Регистрация: 09.12.2009
Сообщений: 14
11.12.2009, 07:32  [ТС] #3
Fatal error c1083:cannot open include file: 'iostream.h':no such file or directory

Что это?? Что делать?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 07:46 #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
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
#include<iostream>
#include<windows.h>
using namespace std;
bool prov_prost(int a, int b)
{
        int temp;
        if(a>b)
        { 
                temp=a;
                a=b;
                b=temp;
        }
        if(a==b)
                return false;
        for(temp=2; temp<=a; temp++)
                if(a%temp==0 && b%temp==0)
                        return false;
        return true;
}       
int main()
{   
        int i, j, n, *temp, *mas, *itog, count_itog=1;
        bool fl=true, fl1;
        SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
        cout<<"Введите размер массива натуральных чисел :";
        cin>>n;
        temp=new int[n];
        mas=new int[n];
        itog=new int[n];
        cout<<"Введите числа массива"<<endl;
        for(i=0; i<n; i++)
        {
                cin>>mas[i];
                temp[i]=1;
                itog[i]=0;
 
        }
        itog[0]=1;
        while(fl)
        {
                fl=false;
                for(i=0;!fl && i<n; i++)
                        if(temp[i]==1)
                                fl=true;
                fl1=true;
                for(i=0; fl1 && i<n-1; i++)
                        for(j=i+1; fl1 && j<n; j++)
                                if(temp[i]!=0 && temp[j]!=0)
                                        fl1=prov_prost(mas[i], mas[j]);
                if(fl1)
                {
                        j=0;
                        for(i=0; i<n; i++)
                                if(temp[i]!=0)
                                        j++;
                        if(j>count_itog)
                        {
                                for(i=0; i<n; i++)
                                        itog[i]=temp[i];
                                count_itog=j;
                        }
                }
                temp[0]--;
                for(i=0; i<n; i++)
                        if(temp[i]<0)
                        {
                                temp[i]=1;
                                temp[i+1]--;
                        }
        }
        for(i=0; i<n; i++)
                if(itog[i]!=0)
                        cout<<mas[i]<<" ";
        cout<<endl;
 
        return 0;
}
0
Лемур
0 / 0 / 0
Регистрация: 09.12.2009
Сообщений: 14
11.12.2009, 08:14  [ТС] #5
Теперь работает. только он выдает подмножество а потом еще строчку из каких то непонятных символов...это нормально?

Добавлено через 6 минут
Ой все..поняла. Спасибо за помощь
0
Лемур
0 / 0 / 0
Регистрация: 09.12.2009
Сообщений: 14
11.12.2009, 18:27  [ТС] #6
а вы не могли бы в кратце объяснить какой цикл что выполняет....
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 18:50 #7
Давайте тогда так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool prov_prost(int a, int b) // функция, которая определяет a и b взаимнопростые числа или нет? (если да то она возвращает true, если нет то false) 
{
        int temp;
        if(a>b)          // в этой и пяти нижеследующих строчках,из двух чисел a и b делаем сравнение и если нужно перестановку, так что бы a было меньше b
        { 
                temp=a;
                a=b;
                b=temp;
        }
        if(a==b) // если a и b равны, сразу возвращаемся из функции с результатом false (значит эти два числа не взаимопростые)
                return false;
        for(temp=2; temp<=a; temp++) // перебираем значение temp
                if(a%temp==0 && b%temp==0) // если в какой-то момент оказалось, что на одно и тоже число temp делятся без остатка и a и b, то возвращаем false (это значит что a и b не взаимопросты)
                        return false;
        return true; // если дошли до этой строки, значит a и b взаимопростые числа, поэтому возвращаем true
}
Теперь основная часть. Наверное проще будет объяснить сам алгоритм. Решение этой задачи вижу только в простом переборе набора из начальных чисел. Перебор сделан так. Создан массив temp[n] размерностью как и массив с числами, и изначально он заполняется единицами. Затем, как с двоичными числами, мы отнимаем всегда единицу. Т.е. элементы массива выглядят так:
1 1 1 1 1 1
0 1 1 1 1 1
1 0 1 1 1 1
0 0 1 1 1 1
1 1 0 1 1 1
и т.д. до (0 0 0 0 0 0)
Т.е. мы в данном массиве перебираем все комбинации единиц и нулей.
Эти комбинации мы используем для выбора самого большого подмножества элементов из массива mas[]. Например, при комбинации 1 0 0 1 1 1, мы проверяем на взаимопростоту числа массива mas[] с индексами 0, 3, 4, 5.
Если находим очередной набор, с большим кол-вом элементов (и в котором все элементы взаимопросты), чем встречались ранее, сохраняем этот набор в массиве itog[]
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2009, 18:50
Привет! Вот еще темы с ответами:

Найти, какое значение встречается в данном массиве наибольшее число раз - C++
я ток что в универ поступил)) раньше с си++ ничего общего не имел)) и попал в очень сильную группу по программированию.. учительница очень...

В массиве объектов класса найти фамилию сборщика, собравшего наибольшее число изделий - C++
Вообщем вот условие. Создать класс, содержащий сведения о количестве изделий, собранный сборщиками цеха за неделю. Класс должен содержать...

Найти наибольшее число в массиве, которое повторяется по крайней мере 2 раза, но не более чем 3 раза - C++
подскажите с задачкой пожалуйста Найти наибольшее число в массиве, которое повторяется по крайней мере 2 раза, но не более чем 3 раза....

Найти подмножество множества - C++
Программа должна позволять вводить с клавиатуры множество чисел, и находить подмножество множества. Т.е например если введено множество...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.12.2009, 18:50
Ответ Создать тему
Опции темы

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