Программирование, т. 5.1.

char *s_source[] = { "01234", "01234", "01234", "" };
 int n = sizeof(s_source) / sizeof(char*);
 char **s=new char*[n];
 for(int i=0;i<n;++i){
	 s[i]=new char[15];
	 strcpy(s[i],s_source[i]);
 }

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

// мои
char *s1[] = {"ab","abcd",""," "};
char *s2[] = {"ab","abccd", "  ", "asda"};

Подскажите

 

Дана последовательность a1, a2, ..., an

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

n=13

это где ты такую задачку выкопал?

перебором проще всего написать

задали на дом

еще нужно, чтобы программа не выполняла лишнюю работу

т.е. если после какой-нибудь проверки элемента как первого члена итоговой последовательности, в эту последовательность вошли последующие элементы, то не проверять эти последующие элементы, как первые члены последовательности

тут без перебора при всём желании никак не сделать

единственное что можно сделать чтобы не было "лишней работы" - оптимизировать этот перебор

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

твои это какие?

и код проверки какой

короче всё сразу кидай

лучшеее выступление за последнюю неделю

1:06:45

нет, спасибо

нп

Подскажите

 

Дана последовательность a1, a2, ..., an

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

n=13

10 sec google

http://ru.wikipedia.org/wiki/Задача_поиска_наибольшей_увеличивающейся_подпоследовательности

какой-то хуевый алгоритм там приведен

какой может быть бинарный поиск в неотсортированном массиве?

Ну отсортируй, сложность то не поменяется

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

Если он ее отсортирует, ответ будет 0

class MaximumIncreasingSequence
{
	int[] Sequence;

	// на входе 13 и 35
	public MaximumIncreasingSequence(int N, int limit)
	{
		int[] seq = new int[N];

		Random r = new Random(2013); // дебажил на конкретном массиве

		for (int i = 0; i < N; i++)
			seq[i] = r.Next(1, limit);

		Sequence = seq;
	}

	public int CountK()
	{
		int Result = Sequence.Length;

		for (int i = 0; i < Sequence.Length; i++)
		{
			int j = i, excluded = i;

			int last = Sequence[j];

			while (j < Sequence.Length)
			{
				if (excluded >= Result)
					break;

				if (Sequence[j] < last)
					excluded++;
				else
					last = Sequence[j];

				j++;
			}

			if (excluded < Result)
				Result = excluded;
		}

		return Result;
	}
}

но этот алгоритм слишком прямолинен и будет в говне при хитрой последовательности скажем 1, 2, 20, 3, 4, 5, он не найдёт последовательность 12345, только 1 2 20 или 3 4 5 - и в ответе я получал только тройку

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

типа такого

1, 2, 20, 3 ... // не исключает ничего и в лоб ищет до конца останавливаясь только на меньших последнего числах

1, 2, 20, 3 ... // исключает первое число и так же идёт дальше

1, 2, 20, 3 ... // исключает первые два

1, 2, 20, 3 ... // исключает 1 и 3

...

1, 2, 20, 3 ... // исключает второе

1, 2, 20, 3 ... // исключает 2-3

(первое, втрое = числа после стартового индекса, т.е. по факту второе, третье)

если не лень будет, то попробую что-то изобрести, чето меня аж зацепило .-.

о, помню решал кучу похожих задач, пойду поищу на местном acm'е

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

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

во-вторых, можно сделать кучу мелких, но в бОльших масштабах экономящих время заглушек, например заставить его никогда не исключать число из поиска если оно на 1 больше предшественника или если подряд два одинаковых числа, то второе исключать всегда

надо сперва отсортировать массив

а потом сравнивать результаты с неотсортитрованным, и выкидывать лишнее

надо сперва отсортировать массив

а потом сравнивать результаты с неотсортитрованным, и выкидывать лишнее

это типа искать каждую возможную комбинацию из отсортированого массива в пределах оригинального, как ты себе это вообще представляешь?

рекурсивно сопостовлять элементы

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

результаты сравнить

да это будет работать чуть ли не дольше обычного полного перебора

зачем перебирать паралельно 2 массива если можно перебирать один с точно теми же задачами, только не имея заранее заданых последовательностей? (которые я не совсем понимаю зачем вообще нужны, если 2 всегда меньше 3, а 5 больше 4)

к слову, тот "неполноценный" алгоритм при 13 чисел 1-35 всегда справляется за 1+/-0.1мс, если полный перебор будет занимать много времени, то возможно будет смысл сначала за 1 мс прогнать массив в кастрированом режиме чтобы изначально задать какое-нибудь минимальное число и облегчить работу полному перебощику

class MaximumIncreasingSequence
{
	int[] Sequence;
	static Random r = new Random();

	public MaximumIncreasingSequence(int N, int limit)
	{
		int[] seq = new int[N];

		for (int i = 0; i < N; i++)
			seq[i] = r.Next(1, limit);

		Sequence = seq;
			//new int[] { 1, 2, 20, 3, 4, 5, 15, 16, 17, 18, 18 };
	}
	public string Seq
	{ get { string res = ""; foreach (int s in Sequence) res += s + " "; return res.Trim(); } }

	int Result = 0;

	public string CountK()
	{
		Result = Sequence.Length;
		DateTime start = DateTime.Now;

		CountNext(0, 0, 0);
		for (int i = 1; i < Sequence.Length; i++)
			CountNext(i, i, Sequence[i]);

		TimeSpan ts = (DateTime.Now - start);

		return string.Format("Res: {0}, time {1} ms;", Result, ts.TotalMilliseconds.ToString());
	}

	private void CountNext(int currentIndex, int excludedNumbers, int last)
	{
		if (excludedNumbers >= Result)
		{
			return;
		}
		if ((currentIndex + 1) >= Sequence.Length)
		{
			// lastitem
			if (Sequence[currentIndex] <= last)
				excludedNumbers++;

			if (excludedNumbers < Result)
				Result = excludedNumbers;

			return;
		}

		if (Sequence[currentIndex] <= last)
		{
			CountNext(currentIndex + 1, excludedNumbers + 1, last);
		}
		else
		{
			CountNext(currentIndex + 1, excludedNumbers, Sequence[currentIndex]);
			CountNext(currentIndex + 1, excludedNumbers + 1, last);
		}
	}
}

результат за 0.9-1.2 мс

и вроде как всё правильно работает

а то когда я оба варианта гонял на один и тот же массив, то прошлый алгоритм ещё и иногда находил вариант на 1 вычеркнутое число меньше, лень было копаться где именно пробел в коде, я тупо вручную перепроверил два таких багнутых вывода - не нашёл ни одной реальной последовательности которая как оно уверяло меня существует, поэтому похуй на него вообще

CountNext(0, 0, 0);
for (int i = 1; i < Sequence.Length; i++)
   CountNext(i, i, Sequence[i]);

мне только вот это не нравится, стартовые вызовы т.е.

в упор не понимаю почему, но такое чувство что что-то тут не так

самый простой варик - это полный перепор по массивам с отброшенным N элементов

не думаю что есть вариант проще этого

 class MaximumIncreasingSequence
 {
int[] Sequence;
static Random r = new Random();
int Result = 0;

public MaximumIncreasingSequence(int N, int limit)
{
  Sequence = new int[N];

  for (int i = 0; i < N; i++)
	Sequence[i] = r.Next(1, limit);
}
public string TxtSeq
{ get { string res = ""; foreach (int s in Sequence) res += s + " "; return res.Trim(); } }

public string CountK()
{
  Result = Sequence.Length;

  for (int i = 0; i < Sequence.Length; i++)
	CountNext(i, i, 0);

  return string.Format("Res: {0}", Result);
}

private void CountNext(int currentIndex, int excludedNumbers, int last)
{
  if (excludedNumbers >= Result)
	return;

  if (currentIndex >= Sequence.Length - 1)
  {   // lastitem
	if (Sequence[currentIndex] <= last)
	  excludedNumbers++;
	if (excludedNumbers < Result)
	  Result = excludedNumbers;
	return;
  }

  if (Sequence[currentIndex] > last)
  {
	CountNext(currentIndex + 1, excludedNumbers, Sequence[currentIndex]);
  }
  CountNext(currentIndex + 1, excludedNumbers + 1, last);
}
 }