Версия для печати темы

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

Форум «Всё о Паскале» _ Задачи _ Возрастающая последовательность

Автор: bioh 15.03.2007 13:33

Задача такая:
Из данного массива удалите 4 таких элемента, чтобы оставшиеся элементы оброзовывали строго возрастающую последовательность

Т.пример: 5,2,8,10,9,14,20,18,23,48,30,32
Отредактированный массив: 5,8,10,14,20,23,30,32
Удаленные элементы: 2,9,18,48

Препод сказал, что последовательность может быть любая, а удалить надо только четыре элемента.

Помогите пожалуйста с идеей, буду очень благодарен.

Заранее всем спасибо.

Автор: volvo 15.03.2007 13:38

Цитата
Препод сказал, что последовательность может быть любая, а удалить надо только четыре элемента.
Тогда попроси у него вот из такой последовательности:
10, 9, 8, 7, 6, 5, 4, 3, 2, 1

удалить ровно 4 элемента, чтобы она стала строго возрастающей...

Автор: bioh 15.03.2007 13:43

Я понимаю, что условие звучит глупо, но я все-таки думаю, что здесь предпологаеться последовательность из которой надо удалить 4 эл-та и она станет возрастающей

Добавлено через 7 мин.
Лично у меня напрашиваеться только одно решение:
поочередное сравнение пары элементов, если a[i]>a[i+1], то запомнить, его номер и потом удалить.

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

Автор: volvo 15.03.2007 13:52

Вообще-то решение задач такого типа описано вот тут: http://algolist.manual.ru/olimp/rec_sol.php#a20

(сама задача - здесь: http://algolist.manual.ru/olimp/rec_prb.php под номером 20)

Автор: bioh 15.03.2007 14:01

Огромное спасибо

Решение накрученное, в динамическом програмировании ничего не понимаю, но все равно огромное спасибо !

Автор: bioh 17.03.2007 14:35

Помоги плз, у меня ничего не вышло
Наверное нужен, совершенно другой подход, нежели этот

Код
#include "stdafx.h"
#include <conio.h>
#include <stdio.h>
int _tmain(int argc, _TCHAR* argv[])
{
    const int xMax=12, yMax=4;
    int x[xMax]={5,2,8,10,9,14,20,18,23,48,30,32};
    int y[yMax],r[xMax],i,j,k;
    //for (i=0;i<xMax;i++)
    //{
    //    printf("enter value fo x[%d] =",i+1);
    //    scanf("%d",&x[i]);
    //}
    for (i=0;i<xMax;i++) printf("X[%d] = %d\n",i+1,x[i]);
    j=0;k=0;i=0;
    if (x[i]>x[i+1] && x[i]>x[i+2]) {y[j]=i;j++;k++;}
    for (i=1;i<xMax-1;i++)
    {
        if (x[i]<x[i-1] && x[i]<x[i+1] && x[i-1]<x[i+1]) {y[j]=i;j++;k++;};
    }
    if (x[i]<x[i-1] && x[i]<x[i-2]) {y[j]=i;j++;k++;}
    printf("K = %d\n",k);
    for (j=0;j<k;j++) printf("Y[%d] = %d\n",j+1,y[j]);
    for (j=0;j<k;j++) printf("X for delete[%d] = %d\n",j,x[y[j]]);
    int s=0;
    int flag;
    for (i=0;i<xMax;i++)
        {
            flag=0;
            if (y[0]!=i && y[1]!=i && y[2]!=i && y[3]!=i) {r[s]=x[i];flag=1;}
        if (flag!=0) s++;
        }
    for (i=0;i<(xMax-k);i++) printf("R[%d] = %d\n",i+1,r[i]);    
    getch();
    return 0;
}

По задумке препода, должны быть исключены числа : 2,9,18,48 под номерами: 1,4,7,10 соответственно

читал http://algolist.manual.ru/olimp/rec_prb.php, не помогло, не понял.
Буду очень благодарен, если подскажете, как это можно сделать попроще