Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Удаление и сортировка чисел в массиве

10K
07 ноября 2006 года
Omega Red
49 / / 15.10.2006
Есть у меня одна задача:
Даны 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;
}

}



У меня программа находит только те числа, которые делятся между собой. Как сделать так, чтобы программа находила наибольшее количество таких пар, и перебрасывала их в отдельный массив?
Или эту задачу можно как-нибудь по-другому решить? Я даже не знаю алгоритма действия...

63
07 ноября 2006 года
Zorkus
2.6K / / 04.11.2006
Для начала скажи интервал значений каждого числа и N, чтобы можно было прикинуть скорость работы разных алгоритмов.
267
07 ноября 2006 года
Cutty Sark
1.2K / / 17.10.2002
Эта задачка несколько сложнее, чем ты думаешь. :)

Самый тупой способ - перебирать все подмножества твоего изначального множества. Но он потребует 2^N операций, а это очень нехорошо.

Есть алгоритм и пошустрее. Я с удовольствием тебе его опишу, но мне хочется быть уверенным, что это не уйдёт в пустоту. Вот тебе критерий, что ты с ним справишься: ты можешь написать сам сортировку массива за N logN операций? Если да, то я тебе объясню, как решать твою задачу. Кстати, где такие дают?
63
07 ноября 2006 года
Zorkus
2.6K / / 04.11.2006
[QUOTE=Cutty Sark] ты можешь написать сам сортировку массива за N logN операций?[/QUOTE]
#include <algorithm>...;)
267
07 ноября 2006 года
Cutty Sark
1.2K / / 17.10.2002
Надеюсь, понятно, что я имел в виду знание устройства хотя бы одного такого алгоритма и умение записать это на нужном языке программирования? :)
63
07 ноября 2006 года
Zorkus
2.6K / / 04.11.2006
Да, конечно, просто как вы сказали про сортировку, само сорвалось, простите...
10K
07 ноября 2006 года
Omega Red
49 / / 15.10.2006
Вот как допустим я ввожу:
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
И что мне с ними делать?
267
08 ноября 2006 года
Cutty Sark
1.2K / / 17.10.2002
Мда... Ох, не справишься ты, парень, с этим алгоритмом.
Пузырьковая сортировка работает за N^2 операций. А я имел в виду N log N. Дело тут не в самой сортировке, а в сложности алгоритма...

Может тебе всё же полный перебор сделать? Перебираешь все подмножества, проверяешь каждое на то, удовлетворяет оно условию или нет, и выбираешь с максимальным числом элементов... Для N = 5 или 10 этого вполне достаточно... Это для N=1000, например, нужен более быстрый алгоритм.
10K
08 ноября 2006 года
Omega Red
49 / / 15.10.2006
Плоховато с перебором разобрался.
Может вот так имелось в виду?
for (i = 0; i < 5; i++)
for (j = i + 1; j < 5; j++)
{
if (N[j]%N == 0)
c[N[j]]++;
}

Потом искать максимальный элемент среди массива с (в данном случае 16), искать, на что это число делится и выбрасывать оставшиеся числа.

Я правильно понял?
267
08 ноября 2006 года
Cutty Sark
1.2K / / 17.10.2002
Нет, я имел в виду полный перебор всех подмножеств вашего исходного множества.
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. Думаю, дело было так. Препод сказал: "А вот вам задача посложнее. Кто решит, тому сразу зачёт!" "Ура," - обрадовались студенты и тут же полезли за подмогой в Интернет...
10K
08 ноября 2006 года
Omega Red
49 / / 15.10.2006
Ура, я решил эту задачу самостоятельно, только способ наверное неправильный.
Код:
/*
Даны 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;


}


А сортировку NlogN я нашёл, только каковы её преимущества перед пузырьковой, кроме быстроты, непонятно...

2CuttyShark

Твой метод всё-таки мне не до конца понятен, не очень хорошо понимаю, как реализовать... Может когда будет время, напишешь в программном виде...
А дело было совсем по другому: принёс мне друг с другой подгруппы лабораторную работу 4, там было 85 задачи, мне решать нужно было через каждую 14, причём эта была предпоследней 84... Завтра сдам сразу при получении, может 10 получу.

А на зачёт нужна совсем другая задача, причём простая (найти максимальный из чётных элементов до первого нечётного. Что здесь тяжёлого - реализовать варианты со всеми чётными, нечётным впереди чётных и др.). Ну и ещё реферат, который попробую в инете поискать.
267
08 ноября 2006 года
Cutty Sark
1.2K / / 17.10.2002
Я, конечно, извиняюсь, молодой человек, но "решил, но неправильно" - это значит "не решил".

Во-первых, у тебя неправильно организована проверка правильности ввода. Число 1, например, твою проверку не пройдёт, а условию задачи - удовлетворяет. Напротив, число 30 пройдёт твою проверку - но оно не подходит по условию.

Во-вторых, проверка это мелочи, вот сам по себе алгоритм у тебя устроен неправильно. Подсунь-ка ему множество 2,3,6. Он скажет тебе, что ничего выкидывать не надо. Но 2 и 3 друг на друга не делятся.

А в-третьих, не обижайся, но для тебя эта задача сложновата.

Засим откланяюсь.
63
08 ноября 2006 года
Zorkus
2.6K / / 04.11.2006
[QUOTE=Omega Red]

А сортировку NlogN я нашёл, только каковы её преимущества перед пузырьковой, кроме быстроты, непонятно...
.[/QUOTE]
:D Это один из двух критериев любоого алгоритма сортировки - скорость работы и стабильность (т.е. если вы сортируете скажем массив структур по какому то признаку, то элементы с одинаковыми ключами не переставляются)
3.2K
09 ноября 2006 года
Sania
186 / / 28.10.2006
Быстрая сортировка:
В среднем получаем О(N*logN)
Доказано, что при отсутствии дополнительной информации о сортируемых данных алгоритма быстрее не существует.
В худшем, но очень редком случае получим О(N*N)
10K
09 ноября 2006 года
Omega Red
49 / / 15.10.2006
И правда много неправильно. Сегодня сдавал эту лабораторку, нам распределили по другому, тяжёлых задач не было, да и проверяли только сдалека. Моя задача конечно прокатила бы, глубоко никто не рассматривал бы.
Да кстати, кто-нибудь знает, как с помощью функции malloc создать массив структуры. Для обычного массива я знаю
a=(int*)malloc(x*y*sizeof(int))
А для структуры что будет?
242
09 ноября 2006 года
Оlga
2.2K / / 04.02.2006
Цитата:
А для структуры что будет?


наверно так:

 
Код:
(struct example *)malloc(N*sizeof(struct example))


N - кол-во структур
9.5K
12 ноября 2006 года
ROLpogo
80 / / 22.08.2006
Решение задачи:

Код:
#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();
}
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог