Здравствуйте, подскажите, пожалуйста, решение или укажите нужное направление
Var A: array [1..n, 1..n] of real; (n-нечетно). Найти сумму элементов из области матрицы A, отмеченной символом ‘*’: 0 0 0 * 0 0 0 0 0 * * * 0 0 0 * * * * * 0 * * * * * * * 0 * * * * * 0 0 0 * * * 0 0 0 0 0 * 0 0 0
sheka
15.10.2009 23:46
s:=0; for i:=1 to (n div 2)+1 do for j:=(n div 2)+1+1-i to (n div 2)+1-1+i do s:=s+a[i,j]; for i:=(n div 2)+2 to n do for j:=(n div 2)+1-(n-i) to (n div 2)+1+(n-i) do s:=s+a[i,j];
volvo
16.10.2009 1:34
Можно сделать ровно в 2 раза меньше циклов:
s := 0; for i := -(n div 2) to (n div 2) do for j := abs(i) + 1 to n - abs(i) do s := s + arr[i + (n div 2) + 1, j];
Lapp
16.10.2009 9:36
Цитата(volvo @ 15.10.2009 22:34)
Можно сделать ровно в 2 раза меньше циклов
, а можно и совсем без циклов :
const n= 7; m= n div 2 + 1;
var a: array[1..n,1..n]of integer;
function Rhomb(i,j: integer): integer; begin if Abs(i-m)<m-Abs(j-m) then if i=m then Rhomb:= a[i,j]+Rhomb(i-1,j)+Rhomb(i+1,j)+Rhomb(i,j+1) else Rhomb:= a[i,j]+Rhomb(i+(i-m) div Abs(i-m),j) else Rhomb:=0 end;
begin {input a} WriteLn('Rhomb Summ is: ',Rhomb(m,1)); ReadLn end.
Прошу (volvo)) особо не придираться, я в курсе возможных проблем со стеком и вообще эффективности. Это, скорее, хохма , но оно работает! Еще сие можно рассматривать как демонстрацию принципиальной взаимозаменимости циклов и рекурсии во многих случаях.
И еще один любопытный факт, обнаруженный во время тестирования программы.. Если исходную матрицу заполнить всю единицами:
1 1 1 1 1 1 1 1 1 , for i:=1 to n do for j:=1 to n do a[i,j]:=1;
- и составить последовательность результатов при n=1,3,5,7,11,13... , то результат будет такой:
1, 5, 13, 25, 41, 61, 85...
Это прекрасно соответствует формуле:
s=n2/2+0.5
- как и должно быть, если рассмотреть это как площадь, занимаемую ромбом. В этом я не усматриваю особого интереса, но если заполнить матрицу вот так:
1 2 3 4 5 6 7 8 9 , for i:=1 to n do for j:=1 to n do a[i,j]:=i+(j-1)*n;
- то есть, по возрастающей слева направо и сверху вниз - то соответственная последовательность сумм будет вот такая:
1, 25, 169, 625, 1681, 3721, 7225...
- и в ней легко разглядеть квадраты членов первой последовательности . Вот, сижу и думаю: какой в этом скрытый смысл)), и как это можно было бы предсказать без предварительного эксперимента?..
Хм?..
Добавлено через 13 мин. Все, я допер, все оказалось просто (очень помогает пройтись пешком, пусть даже и недолго)). Есть интерес/нужда послушать?
andriano
16.10.2009 11:12
Вот ведь интересно: читаем одно и то же, а прочитываем разное. В условии написано "Найти сумму элементов из области матрицы A, отмеченной символом ‘*’" а не "Найти сумму элементов из области матрицы A, имеющей форму ромба". Т.е. как бы не располагались звездочки, хоть в шахматном порядке, решение надо искать по звездочкам, а не предполагая заранее, что звездочки расположены в виде ромба. Т.е. у нас должно быть две матрицы: одна с числами, а вторая - со звездочками. Решение: 1. Перебираем все элементы матриц, если во второй "*", добавляем к сумме число из первой, если нет - нет. 2. Можно оптимизировать: вместо условного перехода подбираем формулу, которая преобразует "*" в 1, а "0" в 0, и складываем все произведения чисел из первой матрицы и результатов формцлы из второй. Теоретически можем получить выигрыш в скорости в несколько (до 10) раз. Хотя, думаю, автору темы это неинтересно.
Для первого варианта:
const n= 7;
var a: array[1..n,1..n]of real; b: array[1..n,1..n]of char;
var i,j : integer; summ : real; begin {input a,b} summ := 0.0; for i := 1 to n do for j := 1 to n do if b[i,j] = '*' then summ := summ + a[i,j]); WriteLn('Rhomb Summ is: ',summ); ReadLn end.
Да, посмотрел по условию - массив чисел вещественный. Поправил.
Быстрый вариант:
for i := 1 to n do for j := 1 to n do summ := summ + a[i,j]*byte(b[i,j]='*');
PS. На компе, с которого я сейчас пишу, нет ни одного компилятора Паскаля, поэтому приведенный мною текст программы прошу рассматривать как написанный на псевдокоде.
Lapp
16.10.2009 11:53
andriano, как всегда, верен себе))
Цитата(andriano @ 16.10.2009 8:12)
читаем одно и то же, а прочитываем разное.
Угу. Потому что мы не finereader'ы, и можем читать не только строки, но и между)). Ни о какой второй матрице - ни слова, а звездочками отмечен - ромб . Убедительная просьба мне не возражать прямо сейчас - давай дождемся автора темы, пусть он скажет.
P.S.
Цитата(andriano @ 16.10.2009 8:12)
PS. На компе, с которого я сейчас пишу, нет ни одного компилятора Паскаля, поэтому приведенный мною текст программы прошу рассматривать как написанный на псевдокоде.
- достаточно написать, что код не проверен. Не надо никаких хитрых псевдокодов - ты говоришь О Паскале, В разделе про Паскаль, С человеком, изучающим Паскаль, И, наконец, заключаешь все в паскалевские теги. И грубые ошибки (типа элемента массива в качестве параметра цикла) недопустимы в любом случае при объяснениях (говорю как администратор)).
valerosha
16.10.2009 14:03
В условии ничего не сказано про вторую матрицу, так что речь скорее всего про ромб. Всем спасибо за ответы! Просто супер!
koda
2.03.2010 13:36
А как на счет такой матрицы (условия задачи: Найти сумму элементов из области матрицы, отмеченной символом * (диагонали входят в выделенную область)
тут походу точно должно быть две матрицы, или я ошибаюсь? Помогите мне разобраться с такой задачкой.
volvo
2.03.2010 15:48
Цитата
тут походу точно должно быть две матрицы, или я ошибаюсь?
И здесь все делается теми же двумя циклами:
for i := 1 to n div 2 + n mod 2 do for j := i to n - i + 1 do begin s := s + a[i, j]; if i <> n div 2 + n mod 2 then { Чтобы центральный элемент не посчитать дважды } s := s + a[n - i + 1, j]; end;
koda
3.03.2010 20:22
Почему то не получается, не могу разобраться, помогите. И в массив забивать можно любые числа или нет? К примеру: 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 0 5 6 7 8 9 0 1 6 7 8 9 0 1 2 7 8 9 0 1 2 3
или же как по условию, с нулями где и должны стоять.
Program Massivzv; const n=7; var a:array[1..n, 1..n] of real; i, j, s: integer; begin assign(input, 'massivzv.in'); reset(input); assign(output, 'massivzv.out'); rewrite(output) for i := 1 to n div 2 + n mod 2 do for j := i to n - i + 1 do begin s := s + a[i, j]; if i <> n div 2 + n mod 2 then { Чтобы центральный элемент не посчитать дважды } s := s + a[n - i + 1, j]; end;
volvo
3.03.2010 20:33
Читать матрицу из файла не пробовал?
На данный момент все, что ты пытаешься сделать - это складывать нули, которыми матрица инициализируется при старте программы по умолчанию. Этого можешь не делать, я тебе и так скажу, ответ будет "0". Удивительно, правда?
К тому же ты еще и не выводишь ничего никуда, так что откуда ты вообще знаешь, получается у тебя что-то или нет? Телепатия?
Но самое главное - это сделать так, чтоб программа хотя бы откомпилировалась. Ошибки-то исправь, синтаксические. Где-то точку с запятой забыл, где-то еще что-то...
Цитата
Почему то не получается
Очень емкое описание ошибки. Хочешь получать такие же ответы? "Потому что внимательнее надо быть."
P.S. Сравни тот код, который привел я с тем, который привел ты. Как ты думаешь, какой проще читается? Выдели свой код тегами...
koda
4.03.2010 20:33
Помогите мне добить этот пример, не могу сооброзить, что куда. Я ведь только учусь... буду очень благодарен.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.