Задача про треугольник Паскаля.

[Mangust]

Народ помогите срочно решить задачу 3.03.2009 уже сдавать надо.

В общем есть треугольник Паскаля, в каждой строке a нечётных чисел. Строки нумеруются с 0. Определить кол-во нечётных чисел в строке № b. Я видел решение в несколько строк без процедур, но забыл. Там было while, в условии цикла and между числами (не логическими выражениями!!), этот цикл считал какое-то число, а ответ выводился "2 shl <это число>".

Помогите плиз, а то срочно надо. Номер строки до 2 000 000 000, чтобы работало быстро просто летало.

[Тупой]

Вопрос на засыпку:
Вы знаете сколько вообще ВСЕГО чисел в строчке треугольника Паскаля под номером 2 000 000 000?
ПС: если скажете, то обещаю написать на C/C++/C#/VB/Pascal/Delphi/... до 3-го марта.

[Plague]

интересная задача (люблю такие).

var n,k,i:longint;
begin
  readln(n);
  k:=0;
  repeat
    if n mod 2=1 then k:=k+1;
    n:=n div 2;
  until n=0;
  n:=1;
  for i:=1 to k do n:=n shl 1;
  writeln(n);
end.

[Тупой]

Plague, ну а при номере строчки = 2 000 000 000 работает?

[Plague]

не работает только уже начиная от 2147483647
это граница типа longint

[Тупой]

А вот мне кажется, что колличество нечетных чисел можно вычислить с помощью простой формулы. Только вот надо подумать, какой...

[Plague]

Ну никто вам не мешает. Думайте...

[Mangust]

Спасибо огромное Plague - прога работает очень помогло.

[Тупой]

(все мое ИМХО, хотите верьте, хотите нет)
Можно сделать немного более простую и быструю функцию, если учитывать тот факт что:
В треугольнике Паскаля
Рассмотрим множество строк от строчки под номером 2^n до строчки под номером 2^(n+1). (давайте считать, что n - "велико")
Число этих строк = 2^n
Так как n велико, то давайте разделим 2^n на четверки (этих четверок будет 2^(n-2))
Теперь я попробую объяснить индуктивно то, до чего додумался:
давайте абстрагируемся от всяких строчек, а просто попробуем составить последовательности:

Например - самое порстое: Пусть дана последовательность
1:{2,4,4,8}
Следующую будем строить предыдущую, умноженную на 2:
2:{2,4,4,8}, {4,8,8,16} - Она уже состоит из 2-х четверок
3: Третья должна состоять из 4-х четверок, которые получаются из предыдущей последовательности следующим образом:
к предыдущей последовательности дописывается сначало все кроме первой четверки, а последняя четверка на равна предпоследней, умноженной на 2(оч непонятно, но по другому никак)
{2,4,4,8}, {4,8,8,16},{4,8,8,16},{8,16,16,32}
4:{2,4,4,8}, {4,8,8,16},{4,8,8,16},{8,16,16,32}, {4,8,8,16},{4,8,8,16},{8,16,16,32}, {16,32,32,64}
...
Для i-й писать влом.
А теперь, я утверждаю, что для номера строчки из треугольника Паскаля = 2^n, числа нечетных чисел в строках с номерами от 2^n до 2^(n+1) записываются как вышеизложенная мною строчка с номером n-1

Завтра могу написать прогу. Преимущество в том, что она сама "строит" треугольник и считает в нем в нечетные числа.

Может я где то ошибся, если что, исправьте.

[Plague]

проверил программу на числе9223372036854775807
верхняя граница Int64 решается за сотую долю секунды.

Суть не в том чтобы построить треугольник он нам не нужен,
просто есть закономерность по которой можно найти количество нечетных чисел в строке треугольника Паскаля.