Object

Бла-бла, не верю никому. Посмотрите внимательней на оценки, например, на 91 балл. Как бы 90 - это понятно. А эта единичка точно была заработана? Или Кумландер её поставил, чтобы у человека была 5? Кумландер может сколько угодно ворчать в блоге и на лекциях, но: 1) свою часть предмета он знает (те области интересов, которые он честно перечислил в своём CV); 2) никого он не валит.

Infern0, да, проще всего с рекурсией (можно ещё конечным автоматом, чтобы итеративно, но тут задача просто написать алгоритм, а не самую быструю реализацию).

Условие а) a[i] != i, для любого i = 0...N
Условие b) abs(a[i+1]-a[i]) > 1 для любого i = 0..(N-1)

Ты написал как бы проверки существующего массива на ошибки. Проще же написать алгоритм так, чтобы цифры добавлялись по одной в конец текущего массива. Нужно хранить множество оставшихся неиспользованных цифр. Таким образом, при добавлении сразу проверяется, попадает ли цифра на то место, которое она обозначает и какова разность с левым соседом (правого ещё нет). См. слайды по алгоритмам, 4-я лекция, otsingupuu.

Задания были очень похожи на те, что образцовом экзамене. Было следующее:

1. Даны 4 пары функций. Для каждой пары надо написать, как первая относится к классу сложности второй. Т.е f(x) = o(g(x)) или f(x) = ω(g(x)) или f(x) = ο(g(x)). Вместо "=" – перевёрнутое "э".

2. Написать алгоритм, который брал бы входными данными число N (< 10) и генерировал бы такую пермутацию из цифр 0....N, что:

а) Любая цифра не стоит на месте, которое она обозначает. Например, в 1203 цифра 3 стоит на 3-ем месте (если считать с нуля). Такую нельзя.
б) Разность между двумя соседними цифра должна быть больше 1.
в) Число, которое эта пермутация обозначает, должно быть наименьшим. Например, если сгенерировалось 3102 и 2013, то нужно предпочесть последнее.

Использовать алгоритм с backtracking и отсечением. За другой алгоритм снижают баллы. Потом надо оценить сложность алгоритма, который сам же написал.

3. На хэщ-таблицы. Вставить в хеш-таблицу данные числа и числа, которые получаются из твоего матрикуля. Хэш-функции первая и вторая, для коллизий, даны. Потом надо удалить числа. Это был open adressing, надо ещё написать его преимущества. Далее, во второй части надо написать функцию вставки ключа в хэш-таблицу, где используется chaining. Прототип функции дан.

4. Где-то 5 теоретических вопросов, типа "Какие сложности возникают при динамическом планировании?", "Чем бинарное дерево поиска отличается от бинарной кучи?", "Как можно доказать, что у какой-то задачи нет алгоритмического решения?".

Catherinka, одинаковые варианты, вот пусть люди и сверяют, кто правду говорит, а кто нет.

Вариант:

// datesdiff

#include <stdio.h>

const int MonthDays[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline int absi(int i)
{
	if (i < 0) return -i; else return i;
}

inline int y366(int year)
{
	return !(year % 4) && ((year % 100) || !(year % 400));
}

int check(int d, int m, int y)
{
	return (
			  (d > 0) && (d < 32) &&  (m > 0) && (m < 13) &&  (y > 0) &&			
			  ((d <= MonthDays[m-1]) || ((m == 2) && (d == 29) && y366(y)))
		   );
}

int diffWithinYear(int d1, int m1, int d2, int m2, int y)
{
	int i, days = d1;
	for (i = m2; i < m1; i++) days += MonthDays[i-1];
	if (m1 > 2 && m2 <= 2 && y366(y)) days++;
	days -= d2;
	return days;
}

int main()
{
	char buff[1024];
	int d[2], m[2], y[2], diff = 0, i, b = 0;
	printf("Date format DD MM YYYY\n");	
	   
	for (i = 0; i < 2; i++)
	{
		printf("Enter date #%d: ", i+1); 
		gets(buff);				   
		while (sscanf(buff, "%d %d %d", &d[i], &m[i], &y[i]) != 3 || !check(d[i], m[i], y[i]))
		{
			printf("Invalid date, re-enter: ");
			fgets(buff, 1024, stdin);
		}
	}		
	   
	if (y[0] == y[1] && m[0] == m[1])
	{		
		diff = absi(d[0] - d[1]);
	}
	else if (y[0] == y[1])
	{
		if (m[1] > m[0]) b = 1;
		diff = diffWithinYear(d[b], m[b], d[1-b], m[1-b], y[0]);
	}
	else // (y[0] != y[1])
	{
		if (y[1] > y[0]) b = 1;
		diff += diffWithinYear(d[b], m[b], 1, 1, y[b]);
		diff += diffWithinYear(31, 12, d[1-b], m[1-b], y[1-b]);
		for (i = y[1-b]+1; i < y[b]; i++)
		{
			diff += 365;
			if (y366(i)) diff++;
		}
		diff++;
	}
		
	printf("The number of days between %02d.%02d.%d and %02d.%02d.%d is %d", 
		d[0], m[0], y[0], d[1], m[1], y[1], diff);
	
	return 0;
}

S-talker, не, ну не совсем ведь бред.

Если брать спектры 3х2 такие, что в вероятности только вида d.dd, т.е. 0.00, 0.01, 0.02, .., 0.99, 1.00, а маргинальные законы вида d.d, то всего можно сгенерировать 94776 спектров, из них компоненты будут независимыми только у 726. Так что с независимыми компонентами подобрать сложнее.