Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++] Задача на массив

Автор: Tanzilit 29.11.2007, 15:50

Здравствуйте господа программисты! Огромная просьба помочь решить! Есть задача:
дано - массив целых,положительных,ограниченных сверху чисел.Определить наиболее часто встречающуюся подряд тройку чисел
Желательно на C или C++

Автор: orthrus 29.11.2007, 19:20

Вот протестируй:

Код


#include "iostream.h"
#include "conio.h"

int main(int argc,char* argv[])
{
 int arr_size = 40;
 int *array = new int[arr_size];
 int border = 3;
 
 std::randomize();
 int max = 0;
 for (int i = 0; i<arr_size; ++i) {
     array[i] = std::random(border);
     max = std::max(max,array[i]);
     std::cout << array[i] << " ";
 }
 std::cout << std::endl;

 int *arr_border = new int[max + 1];
 memset(arr_border,0,sizeof(int)*(max + 1));

 for (int i = 0; i<(arr_size - 1); ++i) {
     int j = 0;
     while ((array[i] == array[i + 1]) && (2 != j) && (i<arr_size)) {++j;++i;}
     if (2 == j) {arr_border[array[i]]++;}
 }

 int tmp = 0, j = -1;
 for (int i = 0; i<max + 1; ++i) {
     if (tmp < arr_border[i]){
        tmp = arr_border[i];
        j = i;
     }
 }
 if (-1 == j) {std::cout << "Троек не найдено" << std::endl;}
 else std::cout << j << " - " << "встречается чаще всего" << std::endl;
 getch();
 return 0;
}

Автор: Mihhail 29.11.2007, 19:29

Код

#include<stdio.h>
#include<mem.h>
#include<stdlib.h>

#define MAX 8     //Ограничивающее число
#define MAXMS 1024 //Размер массива

void main()
{
   int i, i1, i2, j, n1, n2, n3;
   int ms[MAXMS], //Наш массив
       kms[MAX][MAX][MAX]; //Массив под комбинации

   //Обнуляем массив
   memset( kms, 0, MAX * MAX * MAX * sizeof(int) );

   //Заполняем массив случайным образом в указанных пределах
   randomize( );
   for( i = 0; i < MAXMS; i ++ )
      ms[i] = random( MAX );

   //Ищем кол-во каждой комбинации
   for( i = 0; i < MAXMS; i += 3 ){
      if( i + 2 > MAXMS ) break;
      kms[ms[i]][ms[i + 1]][ms[i + 2]] ++;
      }

   //Ищем наиболие встречающуюся комбинацию
   for( j = 0, i = 0; i < MAX; i ++ )
      for( i1 = 0; i1 < MAX; i1 ++ )
         for( i2 = 0; i2 < MAX; i2 ++ )
            if( j < kms[i][i1][i2] ){
               j = kms[i][i1][i2];
               n1 = i;
               n2 = i1;
               n3 = i2;
               }

   //Теперь n1 n2 n3 - искомая тройка чисел встречается j раз
   printf( "%d %d %d - %d", n1, n2, n3, j );
}

Если у тебя дана какая то определённая последовательность для массива чисел просто выкинешь заполнение его случайными значениями.

Автор: Tanzilit 29.11.2007, 19:54

Эх спасибо вам огромное.Очень помогли!
Сейчас потестю,заодно разберусь и изучу как все сделано

Автор: Dov 30.11.2007, 00:26

Mihhail, этот цикл,

Код

   //Ищем кол-во каждой комбинации
   for( i = 0; i < MAXMS; i += 3 ){
      if( i + 2 > MAXMS ) break;
      kms[ms[i]][ms[i + 1]][ms[i + 2]] ++;
      }

по-моему, должен выглядеть как-то так:

Код

    //Ищем кол-во каждой комбинации
    for(i = 0; i < MAXMS - 2; i++)
        kms[ms[i]][ms[i + 1]][ms[i + 2]] ++;

иначе, если будет, к примеру, такой массив: ...3, 1, 1, 1, 1, 6.., то посчитает не правильно. А в этом случае ответ должен быть 2.

p.s. Могу ошибиться. smile

Автор: Mihhail 30.11.2007, 12:16

Dov, это мы немного по разному задание поняли. Как я понял, то если три числа посчитаны то они отбрасываются все сразу. А последние одна или две "лишние" цифры, в этом случае, уже не образуют тройку так что и считать их нет надобности. Но такие "лишние" цифры в идеальных условиях домашних заданий врят ли могут появиться, ИМХО, и условие i + 2 > MAXMS так на всякий случай.
Но возможно ты и прав, в том что нужно считать все тройки чисел, независимо входило ли число в другую группу или нет!?... smile

Автор: Tanzilit 30.11.2007, 17:56

снова здравствуйте товарищи! Огромное спасибо за то что не поленились потратить свое время на помощь
сегодня все изучу и протестю.Но есть небольшая проблема...Сегодня еще раз прочел задание,там помимо решения есть пункт
2)метематическое и словарное обоснование алгоритма
Честно говоря я не до конца понял как это сделать.Может подскажете?
Ну хотябы примрено набросайте плизз что нить по этой теме или подскажите как это сделать(может сам допру)
Заранее thanx

Автор: Tanzilit 3.12.2007, 17:24

ну или хоть плиз обьясните что значит "словесное и математическое обоснование алгоритма"
словесное обоснование - это типо описать работу программы? ну тогда все ясно но что значит математическое обоснование?

Автор: Tanzilit 5.12.2007, 03:46

в общем я уточнил
необходимо описание алгоритма проги и желательно формула ее работы(математическая форма)
еще нужно "зависимость числа значащих операций"
далее таблица
размерность массива\колличество операций
помогите плиз!
послеэ того тему можно будет в принципе пометить как выполненную

Автор: Tanzilit 7.12.2007, 00:12

вот обдумываю вс еэто дело
Mihhail
на какой версии си написано? я пока тестил только на досовском Borland c++ 3,1(другие просто не установлены на данный момент) вроде нет ошибок и компилится,но чет он создается(экзешник) и ничгео не выдает.то есть при нажатии Alt-f5 (вроде так) ниче не выводится
наврено надо на другой версии си тестить
и еще - опишите плиз словами работу алгоритма (просто в задании етсь пункт такой - словесное и математическое описание алгоритма),буду благодарен

Автор: Tanzilit 7.12.2007, 02:02

ну и еще вопрос уже ко всем - нужно начертить таблицу по типу
размерность массива| колл-во операций
то етсь грубо говоря отследить,как меняется колличество операций при изменении размерности массива
честно говоря е не знаю даже с чего начать,подскажите плиз как сделать

Автор: Tanzilit 12.12.2007, 00:52

Снова здравствуйте в общем вот вроде чуть чуть вариант Михаила переделал:

Код

#include<stdio.h>
#include<mem.h>
#include<stdlib.h>

#define MAX 4 //ogranihevauhee 4islo
#define MAXMS 256 //Razmer Massiva

void main()
{
int i, i1, i2, j, n1, n2, n3;
int ms[MAXMS], //Our Massive
kms[MAX][MAX][MAX]; //massiv pod kombinazii

//obnulaem massive
memset( kms, 0, MAX * MAX * MAX * sizeof(int) );

//zapolnaem massive slu4aynim obrazom v ukazannih predelax
randomize( );
for( i = 0; i < MAXMS; i ++ )
ms[i] = random( MAX );

//ishem koll-vo kajdoi kombinazii
for( i = 0; i < MAXMS; i += 3 ){
if( i + 2 > MAXMS ) break;
kms[ms[i]][ms[i + 1]][ms[i + 2]] ++;
}

//ishem naibolee vstre4aushuusa kombinaziu
int count = 0; //***
for( j = 0, i = 0; i < MAX; i ++ )
for( i1 = 0; i1 < MAX; i1 ++ )
for( i2 = 0; i2 < MAX; i2 ++ )
{
count++;       //***
if( j < kms[i][i1][i2] )
{
j = kms[i][i1][i2];
n1 = i;
n2 = i1;
n3 = i2;
}
}
for( i = 0; i < MAXMS; i++ )
printf(" %d ", ms[i]);
printf("Razmernost massiva = %d\nkoll-vo operaciy = %d\n",MAXMS,count); //***
//teper n1 n2 n3 - iskomaya troika 4isel vstre4aushayasaя j raz
printf( "%d %d %d - %d", n1, n2, n3, j );
}

Коментарии на латинском тк сдаваться это дело будет в досовском си
просьба
1) проверить работоспособность в соответствии с условием(1 пост темы)
2) проверить верно ли считает колличество операций(как я понял от размерности массива оно не зависит а зависит от ограничивающего числа)
кстати еще вопрос возник - а что данная прога выведет если троек не будет найдено? видимо какой то бред наврно надо подправить...
еще раз спасибо всем кто помогал