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

Как задать правильно условие??? - C++

Восстановить пароль Регистрация
 
MrAleksej
 Аватар для MrAleksej
20 / 15 / 8
Регистрация: 05.12.2010
Сообщений: 251
Записей в блоге: 1
26.03.2011, 15:41     Как задать правильно условие??? #1
Во введенных массивах найти последовательность максимальной длины из элементов, расположенных в порядке возрастания.

Как правильно задать условие в этой задаче???
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
26.03.2011, 16:25     Как задать правильно условие??? #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
#include <iostream>
#include <cmath>
 
#define MAX(x,y) ( ( x > y ) ? ( x ) : ( y ) )
 
using namespace std;
 
 
int main()
{    
    int i, j, N, max, M = 1;
    cin >> N;
    int *A = new int[N];
    int *T = new int[N];
    cin >> A[0];
    T[0] = 1;
    max = 0;
    for (i = 1; i < N; ++i)
    {
        cin >> A[i];
        for (j = i-1; j >= 0; --j)
        {
            if (A[i] > A[j])
               max = MAX(max, T[j]);
        };
        T[i] = max + 1;
        M = MAX(T[i], M);
        max = 0;        
    };
    cout << M;
  
    return 0;
}
Код
Test
Input:
5
3 8 4 6 9
Output:
4 (патаму ша 3 4 6 9)
IrineK
Заблокирован
26.03.2011, 16:26     Как задать правильно условие??? #3
Если последовательность строго возрастает:
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
#include <iostream>
#include <time.h>
#define N 20
using namespace std;
 
int main()
{   srand(time(NULL));
    int i, Array[N], start=0, len=1, max = 0, startMax;
    
    cout<<"Array A:\n";
    for(i=0;i<N;i++)
    {   Array[i]=rand()%20+1;
        cout<<Array[i]<<" ";
    }
 
    for(i=0;i<N-1;i++)
    {   if(Array[i]<Array[i+1])len++;
        else
        {   
            if(len>=max)
            {   max=len;
                startMax=start;
            }
            start=i+1;
            len=1;
        }
    }
 
    cout<<"\nThe longest strictly ascending sequence:\n";
    for(i=startMax;i<startMax+max;i++)
        cout<<Array[i]<<" ";
    cout<<"\n    length:"<<max;
    
    cin.sync();cin.get();
    return 0;
}
Для монотонно возрастающей последовательности:
C++
1
if(Array[i]<=Array[i+1])len++;
Здесь выводим последнюю из подпоследовательностей максимальной длины, т.к.
C++
1
if(len>=max)
Если хотим вывести первую, тогда:
C++
1
if(len>max)
MrAleksej
 Аватар для MrAleksej
20 / 15 / 8
Регистрация: 05.12.2010
Сообщений: 251
Записей в блоге: 1
27.03.2011, 15:46  [ТС]     Как задать правильно условие??? #4
Спасиб, ребята) ТОлько вот задача(((( Я решил это через функции сделать, и у меня не получается че-то...(((( Где ошибся? Не подскажите?


#include<iostream.h>
#include<iomanip.h>
#include<conio.h>
#include<stdlib.h>
#include <iostream.h>
#include <math.h>
#define MAX(x,y) ( ( x > y ) ? ( x ) : ( y ) )


void inmatr(int[][20],int&,int&);
void outmatr(int[][20],int,int);
void sort(int[][20],int,int);
void main()
{
int x[10][20],n,m,str,k,kol=0; //kol- kol-vo obrabativaemih matric
char ch;
clrscr();
do{
inmatr(x,n,m);
cout<<setw(30)<<"Vvedena matrica:"<<endl;
outmatr(x,n,m);
cout<<"Ukagite nomer sortiruemoj stroki(<"<<n<<"):";
cin>>k;
sort(x,k,m);
cout<<endl<<setw(30)<<"Poluchena matrica:"<<endl;
outmatr(x,n,m);
kol++;
cout<<endl<<"Prodolgit rabotu (y/n)? ";
cin>>ch;}
while(ch=='y'||ch=='Y');
cout<<"Obrabotano matric: "<<kol<<endl;
cout<<"Konec programmi";
getch();
}
void inmatr(int a[][20],int&p,int&q)
{
cout<<"Vvedite razmer matrici:"<<endl
<<"chislo strok(<=10):";
cin>>p;
cout<<"chislo stolbcov(<=20):";
cin>>q;
for(int i=0;i<p;i++)
for(int j=0;j<q;j++)a[i][j]=(rand()-16383)%100;
}
void outmatr(int a[][20],int p,int q)
{
for(int i=0;i<p;i++){
for(int j=0;j<q;j++)cout<<setw(4)<<a[i][j];
cout<<endl;}
}
void sort(int i,int j,int n, int max, int m=1)
{
cin >> n;
int *a = new int[n];
int *T = new int[n];
cin >> a[0];
T[0] = 1;
max = 0;
for (i = 1; i < n; ++i)
{
cin >> a[i];
for (j = i-1; j >= 0; --j)
{
if (a[i] > a[j])
max = MAX(max, T[j]);
};
T[i] = max + 1;
m = MAX(T[i], m);
max = 0;
};
cout << m;

return (0);
}
Yandex
Объявления
27.03.2011, 15:46     Как задать правильно условие???
Ответ Создать тему
Опции темы

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