Автор: 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, не помогло, не понял.
Буду очень благодарен, если подскажете, как это можно сделать попроще