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

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

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

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

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

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

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

C++ Найти, какое значение встречается в данном массиве наибольшее число раз
Найти в массиве наибольшее число подряд идущих одина*ковых элементов. C++
Найти максимальное по числу вершин подмножество C++
C++ Как в динамическом массиве найти наибольшее значение?
Найти подмножество множества C++
Найти в массиве наибольшее число подряд идущих одинаковых элементов C++
Найти наибольшее значение курса доллара в массиве C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 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;
}
Можно и проще, но сегодня голова тяжелая
Лемур
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

Что это?? Что делать?
valeriikozlov
Эксперт C++
4663 / 2489 / 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
Регистрация: 09.12.2009
Сообщений: 14
11.12.2009, 08:14  [ТС]     найти в массиве наибольшее подмножество... #5
Теперь работает. только он выдает подмножество а потом еще строчку из каких то непонятных символов...это нормально?

Добавлено через 6 минут
Ой все..поняла. Спасибо за помощь
Лемур
0 / 0 / 0
Регистрация: 09.12.2009
Сообщений: 14
11.12.2009, 18:27  [ТС]     найти в массиве наибольшее подмножество... #6
а вы не могли бы в кратце объяснить какой цикл что выполняет....
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2009, 18:50     найти в массиве наибольшее подмножество...
Еще ссылки по теме:

C++ В массиве объектов класса найти фамилию сборщика, собравшего наибольшее число изделий
C++ Найти наибольшее число в массиве, которое повторяется по крайней мере 2 раза, но не более чем 3 раза
Найти наибольшее из чисел в массиве C++
Исключить из двух массивов одинаковые значения, и найти в первом массиве наибольшее C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4663 / 2489 / 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[]
Yandex
Объявления
11.12.2009, 18:50     найти в массиве наибольшее подмножество...
Ответ Создать тему
Опции темы

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