Прога на паскале (треугольник Бернулли)
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Прога на паскале (треугольник Бернулли) - 2007-11-24 21:06:22.063333
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
кто не знает этот треугольник приведу пример
1. 1
2. 1 0
3. 0 1 1
4. 2 2 1 0
5. 0 2 4 5 5
6. 16 16 14 10 5 0
На школьной олимпиаде встретилась вывести 16 строк этого треугольника. Я поспорил с одноклассниками что мой алгоритм будет работать быстрее если его я смогу написать. Мой алгоритм высчитывания чисел этого треугольника заключается в следующем: как вы можете выдеть слева в каждой нечетной строке кроме первой, первый элемент строки = 0. Справа в каждой четной строке каждый последний элемент = 0. Так же идут по косой в 4 и 5 строке числа 2 2 а так же в 3 и 4 строке числа 1 1 . я использовал принцип известности двух элементов в каждой последующей строке. и каждый верхний элемент равен модулю разности ниже стоящих элементов окружающих его с двух сторон. Благодаря этой закономерности можно напистаь эффективный алгоритм для 32000 элементов ( максимальное количество элементов массива). Но мои друзья увидели другую закономерность - каждый 1 элемент строки равен сумме всех элементов предыдущей строки. Каждый 2 элемент равен сумме всех элементов предыдущей строки - один первый элемент той самой строки и тп. Вот мы и поспорили чей алгоритм будет работать быстрее. До меня так и не дошло как можно эффективно организовать мой способ. Кто поможет - буду благодарен. И еще подскажите - чей алгоритм работает быстрее - мой или моих друзей-соклассников??
|
|
|
|
|
RE: Прога на паскале (треугольник Бернулли) - 2007-11-24 23:33:17.996666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
эээ… так если всё равно надо выводить все элементы в каждой из шестнадцати строк, то по-моему проще воспользоваться определением треугольника. забубенить цикл, каждая итерация которого будет пробегаться по массиву элементов туда и обратно, при проходе "туда" изменять этот массив чтобы он соответствовал следующей строке, и, заодно, выводить получающуюся строку. При проходе обратно, опять же высчитывать следующую строку и выводить её. собственно проходы "туда" и "обратно" можно объединить просто использовать шаг то +1, то -1, и это, возможно, будет котироваться на олимпиаде, хотя смотря кто будет оценивать…
Или хочется обойтись без массива? По-моему это невозможно, или, по-крайней мере, нерационально: программа станет больше и работать будет дольше. Может памяти будет меньше расходовать, но это уже мелочи.
нну, собственно я бы сделал примерно так:#include <stdio.h>
void print_arr (unsigned long long int v[16], int a, int b)
{
int i;
for (i = 0; i < 15; i ++) {
if (i == a)
printf ("\e[0;31m");
printf ("%4llu,", v[i]);
if (i == b)
printf ("\e[0;39m");
}
printf ("%4llu\n", v[i]);
}
int main ()
{
int line, i;
unsigned long long int v[16] = {
[0 ... 6] = 0, [7] = 1, [8 ... 15] = 0
};
print_arr (v, 7, 7);
for (line = 1; line <= 16/2; line ++) {
for (i = 7 + line; i > 7 - line; i --) {
v[i] += v[i+1];
}
print_arr (v, 7 - line + 1, 7 + line);
for (i = 7 - line; i <= 7 + line; i ++) {
v[i] += v[i-1];
}
print_arr (v, 7 - line, 7 + line);
}
return 0;
}только стоит печатать не весь массив целиком, а прямо во вложенных циклах выводить v[и]. Весь массив – это в отладочных целях.
зы. этот весь код полагается на то, что компилироваться он будет при помощи gcc, и программа будет запускаться в vt100 терминале (linux, ansi, xterm… в MinGW должно пойти без проблем). Терминал нужен для цвета, чтобы было видно где же собственно треугольник.
ззы. кстати а каким компилятором на олимпиаде пользуетесь? если максимальное количество элементов массива == 32000 (32768?) то, надо полагать он 16-ти-битный? А 64-битный целочисленный тип есть? ведь без него сложно представить число 9243752653167856465… Кстати по причине таких чисел, не стоит сильно геморроится о том, чтобы обойтись без массива.
|
|
|
|
|
RE: Прога на паскале (треугольник Бернулли) - 2007-11-25 11:31:02.646666
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
quote:
кстати а каким компилятором на олимпиаде пользуетесь?
Мы олимпиады на обычном паскале катаем. Школьная же ведь олимпиада. И поэтому эта 16 разрядная хрень жутко надоела. Хоть я и не так давно решаю олимпиадные задачки ( где то пол года) но уже вижу траблу в которая заключается в размерности массива. Не всегда удается реально определить эффективность моего алгоритма по сравнению с другими. А так я с++ еще не юзал. Но скоро думаю и на него потихоньку буду переходить… Но вроде по отзывам он сложнее паскаля. У кого есть какие мнения на этот счет? Стоит ли переходить на с++
|
|
|
|
|
RE: Прога на паскале (треугольник Бернулли) - 2007-11-25 22:32:30.310000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: gotoxardas
quote:
кстати а каким компилятором на олимпиаде пользуетесь?
Мы олимпиады на обычном паскале катаем. Школьная же ведь олимпиада. И поэтому эта 16 разрядная хрень жутко надоела.
Что значит "обычном"? В смысле TurboPascal? Гы.
Поставь себе MinGW и в нём fpc – будет тебе 32-битный паскаль.
quote:
ORIGINAL: gotoxardas
Хоть я и не так давно решаю олимпиадные задачки ( где то пол года) но уже вижу траблу в которая заключается в размерности массива.
Зачем тебе массив больше 32768 элементов? Бывает конечно, но… если уж пишешь под дос, то терпи :) 64Kb один сегмент памяти, 16-битрая адресация, и прочие заморочки. В олимпиадах, такое не надо. Но в приведённой задаче, реально нужен 64-битный целый тип. Причём беззнаковый, в знаковый не лезет несколько чисел из последней, 16-ой строки. Хотя… Я чёт вспоминаю, что в турбопаскале, был какой-то целый тип, который на самом деле с мантиссой и в него оччень большие числа влезают, но влезают с погрешностью.
quote:
ORIGINAL: gotoxardas
Не всегда удается реально определить эффективность моего алгоритма по сравнению с другими.
Тут довольно-таки просто. Смотрим на мою программу. Там если внешний цикл, тело которого выполняется N/2 раз, где N – это количество строк, которые надо вывести. Внутри него два цикла, первый выполняется line+1 раз, и второй, который выполняется line+2 раз. Внутри каждого внутреннего цикла одно сложение. На первой итерации внешнего цикла будет выполнено 2 + 3 сложения, то есть 5, на второй 4 + 5 = 9, на третьей 6 + 7 = 13, на N/2 – N + N + 1 = 2*N+1, всё это надо просуммировать, это сумма арифметической прогрессии. если вспомнить формулу для её суммы, то можно увидеть, что самая быстрорастущая при росте N часть – это k*N^2, надо только коэффициент k при ней определить. Вот и получаем, что сложность моего алгоритма – это k*N^2. (точнее О (k*N^2) – `О'-большое от N квадрат, но это уже детали, которые в курсе матанализа объяснят ;) ).
Если взять другое решение, то там, вероятно другая зависимость получиться, но лучше k*N^2 в данном случае не выйдет, вся разница будет в коэффициенте k, так как по-любому надо считать где-то N^2 элементов для N-ной строки. (там N^2 с коэффициентом конечно, как-минимум 1/2 вылезет, но мне просто считать лень).
quote:
ORIGINAL: gotoxardas
А так я с++ еще не юзал. Но скоро думаю и на него потихоньку буду переходить… Но вроде по отзывам он сложнее паскаля. У кого есть какие мнения на этот счет? Стоит ли переходить на с++
Насчёт сложнее – это враньё. Наглая ложь. Ну, точнее C++ – сложнее, он ведь несколько другого класса язык, в нём ООП, классы/шаблоны и проч. А их не только понять надо (что в общем-то не так и сложно), но и научиться ими пользоваться (а это уже в полпинка не выйдет). Но если сравнивать с C, то на мой взгляд – никакой разницы. А всё остальное – это религиозные войны. Я знаю паскалистов, которые почти все поголовно считают, что начинать изучение программирования надо с паскаля, знаю C-шников, которые тоже почти поголовно считают что изучение программирования надо начинать с C. А сам я не знаю. По-моему, asm даже лучше. Он в чём-то проще – никаких тебе циклов, функций, переменных. Команды, регистры, ячейки памяти и адреса этих ячеек. И всё что надо понимать. А дальше тупо сидеть и кодить. Правда, после асма, вероятно, будет сложно втыкать в эти циклы и условия – "глупые" ограничения структурного программирования, но я же втыкал после бейсика, того в котором тоже всё на goto и условия, и циклы и прочее. И ничего, без проблем в общем-то.
|
|
|
|
|
RE: Прога на паскале (треугольник Бернулли) - 2007-11-26 19:15:06.763333
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
Вот наконец то организовал свой алгоритм на паскале. Вот исходники:
uses crt;
var
a:array[1..138] of longint;
b:array[1..16] of integer;
i,j:integer;
k,k1:integer;
begin
clrscr;
for i:=1 to 16 do
begin
k:=k+i;
b[i]:=k+1;
write(b[i],' ');
end;
writeln;
a[1]:=1;
a[2]:=1;
a[3]:=0;
a[5]:=1;
a[6]:=1;
k1:=1;
for j:=3 to 16 do
begin
if j mod 2=1 then
begin
a[b[j-1]]:=0;
a[b[j+1]-2]:=a[b[j]-2];
for i:=b[j+1]-3 downto b[j] do
begin
k1:=k1+1;
a[i]:=a[b[j+1]-k1] + a[b[j]-k1];
end;
end
else
begin
k1:=0;
a[b[j+1]-1]:=0;
a[b[j]+1]:=a[b[j-1]+1];
for i:=b[j]+2 to b[j+1]-1 do
begin
k1:=k1+1;
a[i]:= a[b[j-1]+k1] + a[b[j]+k1];
end;
end;
k1:=1;
end;
k1:=0;
for i:=1 to 16 do
begin
for j:=1 to i do
begin
k1:=k1+1;
write(a[k1]:5);
end;
writeln;
end;
repeat until keypressed;
end.
|
|
|
|
|
|
