профессионалам (задачи при приеме на работу)

[Kukurudza]

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

1. в некой стране принимается денежная реформа. максимальная купюра будет расцениваться в от 1 до 100000 единиц.
известно, что каждая более мелкая купюра должна быть делителем каждой более крупной. например 1 7 14 42.
написать функцию, на вход которой подается номинал максимальной купюры (n), а функция возвращает максимальное количество различных купюр.
будет принято то сочетание, в котором максимальное количество различных купюр.

2. задана строка длиной не более 50 символов.
написать функцию, которая возвращает минимальное количество символов, которое необходимо дописать в конец строки чтобы строка стала симметричной.

на задания давался час

[Syuf]

Я не профессионал, и мне лень писать код, поэтому я могу предложить лишь алгоритм:
1. В массив выписываем делители за O(n), делаем такую линейную по памяти динамику за O(n^2): a[k] - длина макс. посл-ти, заканч. на k-том элементе, a[0] = 1, a[k] = i from [1 .. k-1] max{a[i] + 1}, при a[k] кратном a[i]. Ответ - максимальное число в массиве динамики.
2. Перебор по кол-ву добавляемых символов 1..длины строки, проверка на возможность - поиск нового центра строки и проверка на полиндромность внутренней части.
Задания не трудные, за час вполне.
Это куда собеседование?

[Kukurudza]

еще?
мои решения координально другие.
ку
да, напишу позже

[onewho]

ну 2 вот так решил

int count(std::string s) {

	int counter=0;

	int pos=0;

	std::string::iterator it=s.begin();

	while (it!=s.end()) {
		if (std::equal(it,s.end(),s.rbegin()))
			return counter;

		counter++;
		it++;

	}

	return counter;

}



int main() {

	std::string s = "eegehhhhe";

	std::cout << count(s);



	getch();
	return 0;
}

вродь как даже верно считает.

а, да, про 50 символов не учитывал ограничение, ну и для простоты со string работал, хотя с С-массивом не сложнее было бы.

про 1 попож подумаю))

[Son Of Pain]

Первая задача. Тут решение фактически задано уже в условии:
1) Факторизовать введенное число, сохраняя делители в массиве. Например, для числа 42 результатом будет {1, 2, 3, 7}. Количество элементов в полученном массиве и будет ответом, собсна.
2) Для получения номиналов всех купюр нужно взять единицу, и в произвольном порядке домножать ее на все остальные элементы массива. Но в задаче это не требуется, впринципе, потому хватит и первого пункта.

Ну а для второй решение уже написали в предыдущем комментарии.

[Syuf]

Сообщение от Kukurudza

каждая более мелкая купюра должна быть делителем каждой более крупной

Например, для числа 42 результатом будет {1, 2, 3, 7}. Количество элементов в полученном массиве и будет ответом, собсна.

Если бы все так просто. Нет, это не так.

[Son Of Pain]

Сообщение от Syuf

Если бы все так просто. Нет, это не так.

Читаем внимательнее, там еще и второй пункт есть, в котором написано, как получить номиналы. Делители и номиналы - разные вещи.

[onewho]

чует моё сердце в 1 задаче рекурсия нужна

[Kukurudza]

не, ребят, 1 2 3 7 не канают же. например 7 на 3 не делится.

[Son Of Pain]

И еще раз.

Сообщение от Son Of Pain

2) Для получения номиналов всех купюр нужно взять единицу, и в произвольном порядке домножать ее на все остальные элементы массива. Но в задаче это не требуется, впринципе, потому хватит и первого пункта.

При факторизации получили делители 1 2 3 7.
Взяли единицу, домножаем ее на делители, взятые в произвольном порядке.
Например так:
1*2=2
2*3=6
6*7=42
Итоговые номиналы - 1, 2, 6, 42.

Или так:
1*7=7
7*2=14
14*3=42
Итоговые номиналы: 1, 7, 14, 42.

Ну или так:
1*3=3
3*7=21
21*2=42
Итоговые номиналы: 1, 3, 21, 42.
Есть еще варианты, всего их будет (n-1)! , где n - количество делителей, в приведенном примере это будет 3!=6.