Помогите решить задачку на pascal

[fatalex]

Во-первых, можно и без "Вы", ибо я студЭнт и учусь на 2 курсе. )))

Не вопрос, перешли на "ты"

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

Гм... Не буду спорить, в своей оценке я явно перебрал К сожалению, в свое время нам этого не читали Надо будет восполнить пробел ...

Получается, что сложность моего кода "0". Так ведь?

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

Ну что тут сказать? Жаль ... Сам такое проходил в свое время ...

 

[Sefiroth]

Нам тож не совсем это читали. Просто приходилось кое-чё писать...

Нет, сложность твоего кода M^2... Т.к. формула вычисления числа комбинаций из M по n в общем случае сводится к M^2 (но при малых n или M-n сложность будет стремиться к M - получатся в числителе и знаменателе большие факториалы, которые сократятся)... И с учётом того что операции с большими числами прийдётся реализовывать программно - ещё logM, и того M^2*logM в общем случае и ~M*logM при n->1, n->M-1.

А вот в своём случае я тоже не учёл, что те самые 8-метровые числа, про которые я говорил, мне прийдётся складывать, а это значит, что в цикле операция, сложность которой logM... Поэтому сложность моего алгоритма тоже M^2*logM...

Но с точки зрения теории информации должно быть решение сложности просто M^2 в общем случае, если я ничё не напутал...

 

[efreet]

public class NumbersCount {

	//~ Methods --------------------------------------------------------------------------------------------------------

	public static void main(String args[]) {
		Map<Integer, Set<Integer>> numbers  = new HashMap<Integer, Set<Integer>>();
		int						   tmpValue = 0;

		for (int i = 1; i < 101; i++) {
			tmpValue = i % 3;

			if (!numbers.containsKey(tmpValue)) {
				numbers.put(tmpValue, new HashSet<Integer>());
			}

			numbers.get(tmpValue).add(i);
		}

		System.out.println("result: ");
		System.out.println(numbers);
	}
}

результат

result: 
{0=[69, 3, 6, 66, 9, 78, 12, 72, 15, 75, 84, 87, 18, 81, 21, 93, 24, 27, 90, 30, 33, 99, 39, 96, 36, 42, 45, 51, 48, 54, 57, 63, 60], 1=[1, 70, 4, 64, 7, 67, 76, 10, 79, 13, 73, 85, 16, 19, 82, 22, 25, 94, 88, 28, 91, 31, 34, 100, 97, 37, 43, 40, 46, 49, 55, 52, 58, 61], 2=[68, 2, 71, 5, 65, 8, 77, 11, 14, 74, 17, 86, 80, 20, 83, 23, 92, 95, 26, 89, 29, 35, 32, 98, 38, 41, 47, 44, 50, 53, 59, 56, 62]}

пардон за то, что вмешиваюсь.
Sefiroth, что скажешь о таком решении задачи из первого поста?
реализация на жабе.

 

[fatalex]

2 sefiroth

Нет, сложность твоего кода M^2... Т.к. формула вычисления числа комбинаций из M по n в общем случае сводится к M^2 (но при малых n или M-n сложность будет стремиться к M - получатся в числителе и знаменателе большие факториалы, которые сократятся)... И с учётом того что операции с большими числами прийдётся реализовывать программно - ещё logM, и того M^2*logM в общем случае и ~M*logM при n->1, n->M-1.

Пару слов в защиту. В данном конкретном случае мы считаем выборку по 2 числа, причем числа, в 2 раза меньшего M. В данном случае после сокращений количество сочетаний считается как M*(M-1)/2 - без циклов. Для 10 000 000 получим число около 5*10^13. Тип int64 ограничен 2^63-1 - это около 9*10^18. Для этого случая - хватит, при возрастании чисел, понятно, рано или поздно придется извращаться ...

2 eftreet

пардон, решил ответить тоже ...
проще уж так тогда

const 
  M = 100;
  n = 3;
var 
  startValue,
  currentValue : integer;
begin
  for startValue := 1 to n do begin
    Write(startValue, ' group:');
    currentValue := startValue;               
    while (currentValue <= M) do begin
      Write(currentValue, #9);
      inc(currentValue, n);
    end;
    WriteLn;
  end;
end;

в чем отличие от Вашего примера - не надо проверять содержимое на повторяемость значений. Понятно ведь, что n1 и n2, сравнимые по модулю n, будут отстоять друг от друга на целое количество n ... И хранить эти значения тоже абсолютно незачем.

 

[batu]

Fatalex рулит. Условия не понятны. Есть еще вариант. Может сравнимы по модулю 3 это делящиеся на 3 без остатка? Там же не про пары спрашивают.. Тогда ваще нечего искать..Int(100/3) или плюс один если считать 0.

 

[batu]

А вот если речь о парах, то не прав.
Вдумайтесь, не сколько РАЗНЫХ пар, ни сколько чисел, составляющих РАЗНЫЕ пары, просто - сколько чисел ...
Дык если считать, что 3 и 3 - подходят, к примеру, то таких чисел всегда M. И пофигу M - первых, или начиная с двойки, с тройки ...

Пример: M=5 n=2

Числа 1, 3, 5 - первый сет; 2 и 4 - второй сет. Сколько всего чисел? 5. Т.е. задача или шуточная или некорректно сформулирован вопрос ... Нас ведь не просят узнать кол-во подобных чисел в каждой группе. Просто - сколько всего ...
Я бы и 0 включал. Тогда пар сравнимых только три (0,3) (1,4) (2,5). Если без 0, то две пары, а числа естественно будут перебраны все.. Или их надо повторять при каждом сравнении по модулю?.. Тогда это чушь. Каждое число с сравнимо с каким то по модулю p. Если 2p>=M

 

[batu]

Что, собственно, и доказал eftreet перебрав все числа в особо извращенной форме

 

[maramzin]

>>а где, простите, щас в школе можно найти нормального препода по информатике, который хотя бы подбирает реальные жизненные задачи, и знает хотя бы не меньше своих учеников? )))

Неужели все действительно так плохо?