/*
Даны N положительных целых чисел, которые не делятся ни на какие простые числа,
кроме 2 и 3. Требуется выкинуть минимально возможное количество чисел так,
чтобы из любых двух оставшихся одно делилось на другое.*/
#include "iostream.h"
int i, j, N[7], c[100], max, x;
void main()
{
cout<<"Vvedite elementi massiva, delyasciesya na 2 i 3"<<endl;
for (i = 0; i < 7; i++)
{
cin>>N;
if (N%2 != 0 && N%3 != 0)
{
cout<<"Vvedi drugoe cislo"<<endl;
i--;
}
}
cout<<"Vvedenniy massiv: ";
for (i = 0; i < 7; i++)
cout<<N<<", ";
cout<<endl;
for (j = 0; j < 7; j++)
for (i = j+1; i < 7; i++)
{
if (N%N[j] == 0)
c[N]++;
if (N[j]%N == 0)
c[N[j]]++;
}
for (i = 0; i < 100; i++)
{
max = c[0];
if (max < c)
{
max = c;
x = i;
}
}
cout<<"Nuzno vibrosit cisla ";
for (i = 0; i < 7; i++)
{
if (x%N != 0)
cout<<N<<" ";
}
cout<<endl;
}
Удаление и сортировка чисел в массиве
Даны N положительных целых чисел, которые не делятся ни на какие простые числа, кроме 2 и 3. Требуется выкинуть минимально возможное количество чисел так, чтобы из любых двух оставшихся одно делилось на другое
Вот начатое решение:
Цитата:
#include "iostream.h"
int N[5], i, j;
void main()
{
cout<<"Vvedite elementi massiva, delyasciesya na 2 i 3"<<endl;
for (i = 0; i < 5; i++)
{
cin>>N;
if (N%2 != 0 && N%3 != 0)
{
cout<<"Vvedi drugoe cislo"<<endl;
i--;
}
}
cout<<"Vvedenniy massiv: ";
for (i = 0; i < 5; i++)
cout<<N<<", ";
cout<<endl;
for (j = 0; j < 5; j++)
for (i = j+1; i < 5; i++)
{
if (N%N[j] == 0 || N[j]%N == 0)
cout<<N<<"/"<<N[j]<<endl;
}
}
int N[5], i, j;
void main()
{
cout<<"Vvedite elementi massiva, delyasciesya na 2 i 3"<<endl;
for (i = 0; i < 5; i++)
{
cin>>N;
if (N%2 != 0 && N%3 != 0)
{
cout<<"Vvedi drugoe cislo"<<endl;
i--;
}
}
cout<<"Vvedenniy massiv: ";
for (i = 0; i < 5; i++)
cout<<N<<", ";
cout<<endl;
for (j = 0; j < 5; j++)
for (i = j+1; i < 5; i++)
{
if (N%N[j] == 0 || N[j]%N == 0)
cout<<N<<"/"<<N[j]<<endl;
}
}
У меня программа находит только те числа, которые делятся между собой. Как сделать так, чтобы программа находила наибольшее количество таких пар, и перебрасывала их в отдельный массив?
Или эту задачу можно как-нибудь по-другому решить? Я даже не знаю алгоритма действия...
Для начала скажи интервал значений каждого числа и N, чтобы можно было прикинуть скорость работы разных алгоритмов.
Самый тупой способ - перебирать все подмножества твоего изначального множества. Но он потребует 2^N операций, а это очень нехорошо.
Есть алгоритм и пошустрее. Я с удовольствием тебе его опишу, но мне хочется быть уверенным, что это не уйдёт в пустоту. Вот тебе критерий, что ты с ним справишься: ты можешь написать сам сортировку массива за N logN операций? Если да, то я тебе объясню, как решать твою задачу. Кстати, где такие дают?
#include <algorithm>...;)
Надеюсь, понятно, что я имел в виду знание устройства хотя бы одного такого алгоритма и умение записать это на нужном языке программирования? :)
Да, конечно, просто как вы сказали про сортировку, само сорвалось, простите...
8, 3, 4, 9, 16
Получается
4/8
9/3
16/8
16/4
Как я думаю, нужно убрать числа 9 и 3. Я хотел сделать так, чтобы прога искала значения, и высчитывала, чего больше: 2 и 1/2; или 3 и 1/3. И если у меня первого случая больше, то удаляются числа, делящиеся на 3.
Наверное неправильно, а сортировку какую-то я умею делать, пузырьковая называется. Но от неё толку наверное не будет, получится 3 4 8 9 16
И что мне с ними делать?
Пузырьковая сортировка работает за N^2 операций. А я имел в виду N log N. Дело тут не в самой сортировке, а в сложности алгоритма...
Может тебе всё же полный перебор сделать? Перебираешь все подмножества, проверяешь каждое на то, удовлетворяет оно условию или нет, и выбираешь с максимальным числом элементов... Для N = 5 или 10 этого вполне достаточно... Это для N=1000, например, нужен более быстрый алгоритм.
Может вот так имелось в виду?
for (i = 0; i < 5; i++)
for (j = i + 1; j < 5; j++)
{
if (N[j]%N == 0)
c[N[j]]++;
}
Потом искать максимальный элемент среди массива с (в данном случае 16), искать, на что это число делится и выбрасывать оставшиеся числа.
Я правильно понял?
3,4,8,9,16 - не подходит, 9 не делится на 8
3,4,8,9 - тоже не подходит по той же причине
3,4,8,16 - 4 не делится на 3
3,4,9,16 - тоже
3,8,9,16 - 9 не делится на 8
4,8,9,16 - тоже
4, 8, 16 - подошло!!!
P.S. Думаю, дело было так. Препод сказал: "А вот вам задача посложнее. Кто решит, тому сразу зачёт!" "Ура," - обрадовались студенты и тут же полезли за подмогой в Интернет...
Код:
А сортировку NlogN я нашёл, только каковы её преимущества перед пузырьковой, кроме быстроты, непонятно...
2CuttyShark
Твой метод всё-таки мне не до конца понятен, не очень хорошо понимаю, как реализовать... Может когда будет время, напишешь в программном виде...
А дело было совсем по другому: принёс мне друг с другой подгруппы лабораторную работу 4, там было 85 задачи, мне решать нужно было через каждую 14, причём эта была предпоследней 84... Завтра сдам сразу при получении, может 10 получу.
А на зачёт нужна совсем другая задача, причём простая (найти максимальный из чётных элементов до первого нечётного. Что здесь тяжёлого - реализовать варианты со всеми чётными, нечётным впереди чётных и др.). Ну и ещё реферат, который попробую в инете поискать.
Во-первых, у тебя неправильно организована проверка правильности ввода. Число 1, например, твою проверку не пройдёт, а условию задачи - удовлетворяет. Напротив, число 30 пройдёт твою проверку - но оно не подходит по условию.
Во-вторых, проверка это мелочи, вот сам по себе алгоритм у тебя устроен неправильно. Подсунь-ка ему множество 2,3,6. Он скажет тебе, что ничего выкидывать не надо. Но 2 и 3 друг на друга не делятся.
А в-третьих, не обижайся, но для тебя эта задача сложновата.
Засим откланяюсь.
А сортировку NlogN я нашёл, только каковы её преимущества перед пузырьковой, кроме быстроты, непонятно...
.[/QUOTE]
:D Это один из двух критериев любоого алгоритма сортировки - скорость работы и стабильность (т.е. если вы сортируете скажем массив структур по какому то признаку, то элементы с одинаковыми ключами не переставляются)
В среднем получаем О(N*logN)
Доказано, что при отсутствии дополнительной информации о сортируемых данных алгоритма быстрее не существует.
В худшем, но очень редком случае получим О(N*N)
Да кстати, кто-нибудь знает, как с помощью функции malloc создать массив структуры. Для обычного массива я знаю
a=(int*)malloc(x*y*sizeof(int))
А для структуры что будет?
Цитата:
А для структуры что будет?
наверно так:
Код:
(struct example *)malloc(N*sizeof(struct example))
N - кол-во структур
Код:
#include <string.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
struct SNode
{
int Value;
int Weight;
bool Status;
};
int IsDivide(int a, int b)
{
if ( !(a % b) || !(b % a) )
return 0;
return 1;
}
void main (void)
{
clrscr();
randomize();
SNode Dim[MAXSIZE];
int CurValue;
for (int i = 0; i < MAXSIZE; i++)
{
do
{
CurValue = (random (MAXSIZE * 3) + 1) * (random (2) + 2);
for (int j = 0; j < i; j++)
if (Dim[j].Value == CurValue)
{
CurValue = 0;
break;
}
}
while (!CurValue);
Dim.Value = CurValue;
Dim.Weight = 0;
Dim.Status = true;
printf ("%i: \t%i\n", i + 1, Dim.Value);
}
int ResDivide;
bool ResDivideWasTrue = true;
int MaxID,
MaxWeight;
while ( ResDivideWasTrue )
{
ResDivideWasTrue = false;
for (int i = 0; i < MAXSIZE; i++)
{
if ( Dim.Status )
for (int j = i + 1; j < MAXSIZE; j++)
{
if ( Dim[j].Status )
{
ResDivide = IsDivide (Dim.Value, Dim[j].Value);
if ( ResDivide )
{
Dim.Weight += ResDivide;
Dim[j].Weight += ResDivide;
ResDivideWasTrue = true;
}
}
}
}
if ( ResDivideWasTrue )
{
MaxID = -1;
MaxWeight = 0;
for (int i = 0; i < MAXSIZE; i++)
if ( Dim.Status && (Dim.Weight > MaxWeight) )
{
MaxWeight = Dim.Weight;
MaxID = i;
}
if ( MaxID > -1 )
Dim[MaxID].Status = false;
for (int n = 0; n < MAXSIZE; n++)
if ( Dim[n].Status )
Dim[n].Weight = 0;
}
}
printf ("\n\n");
for (int i = 0; i < MAXSIZE; i++)
if ( Dim.Status )
printf ("%i: \t%i\n", i + 1, Dim.Value);
printf ("\n\n");
printf ("\nWork Finished!");
getch();
}
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
struct SNode
{
int Value;
int Weight;
bool Status;
};
int IsDivide(int a, int b)
{
if ( !(a % b) || !(b % a) )
return 0;
return 1;
}
void main (void)
{
clrscr();
randomize();
SNode Dim[MAXSIZE];
int CurValue;
for (int i = 0; i < MAXSIZE; i++)
{
do
{
CurValue = (random (MAXSIZE * 3) + 1) * (random (2) + 2);
for (int j = 0; j < i; j++)
if (Dim[j].Value == CurValue)
{
CurValue = 0;
break;
}
}
while (!CurValue);
Dim.Value = CurValue;
Dim.Weight = 0;
Dim.Status = true;
printf ("%i: \t%i\n", i + 1, Dim.Value);
}
int ResDivide;
bool ResDivideWasTrue = true;
int MaxID,
MaxWeight;
while ( ResDivideWasTrue )
{
ResDivideWasTrue = false;
for (int i = 0; i < MAXSIZE; i++)
{
if ( Dim.Status )
for (int j = i + 1; j < MAXSIZE; j++)
{
if ( Dim[j].Status )
{
ResDivide = IsDivide (Dim.Value, Dim[j].Value);
if ( ResDivide )
{
Dim.Weight += ResDivide;
Dim[j].Weight += ResDivide;
ResDivideWasTrue = true;
}
}
}
}
if ( ResDivideWasTrue )
{
MaxID = -1;
MaxWeight = 0;
for (int i = 0; i < MAXSIZE; i++)
if ( Dim.Status && (Dim.Weight > MaxWeight) )
{
MaxWeight = Dim.Weight;
MaxID = i;
}
if ( MaxID > -1 )
Dim[MaxID].Status = false;
for (int n = 0; n < MAXSIZE; n++)
if ( Dim[n].Status )
Dim[n].Weight = 0;
}
}
printf ("\n\n");
for (int i = 0; i < MAXSIZE; i++)
if ( Dim.Status )
printf ("%i: \t%i\n", i + 1, Dim.Value);
printf ("\n\n");
printf ("\nWork Finished!");
getch();
}