Помощь - Поиск - Пользователи - Календарь
Полная версия: сумма элементов из области матрицы, отмеченной символом *
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
valerosha
Здравствуйте,
подскажите, пожалуйста, решение или укажите нужное направление

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
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
Можно сделать ровно в 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
Цитата(volvo @ 15.10.2009 22:34) *
Можно сделать ровно в 2 раза меньше циклов

, а можно и совсем без циклов smile.gif :
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.

smile.gif Прошу (volvo)) особо не придираться, я в курсе возможных проблем со стеком и вообще эффективности. Это, скорее, хохма smile.gif, но оно работает!
Еще сие можно рассматривать как демонстрацию принципиальной взаимозаменимости циклов и рекурсии во многих случаях.

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

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...

- и в ней легко разглядеть квадраты членов первой последовательности smile.gif.
Вот, сижу и думаю: какой в этом скрытый смысл)), и как это можно было бы предсказать без предварительного эксперимента?.. smile.gif

Хм?.. rolleyes.gif

Добавлено через 13 мин.
Все, я допер, все оказалось просто smile.gif (очень помогает пройтись пешком, пусть даже и недолго)).
Есть интерес/нужда послушать?
andriano
Вот ведь интересно: читаем одно и то же, а прочитываем разное.
В условии написано "Найти сумму элементов из области матрицы 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
andriano, как всегда, верен себе))
Цитата(andriano @ 16.10.2009 8:12) *
читаем одно и то же, а прочитываем разное.
Угу. Потому что мы не finereader'ы, и можем читать не только строки, но и между)).
Ни о какой второй матрице - ни слова, а звездочками отмечен - ромб smile.gif.
Убедительная просьба мне не возражать прямо сейчас - давай дождемся автора темы, пусть он скажет.

P.S.
Цитата(andriano @ 16.10.2009 8:12) *
PS. На компе, с которого я сейчас пишу, нет ни одного компилятора Паскаля, поэтому приведенный мною текст программы прошу рассматривать как написанный на псевдокоде.
- достаточно написать, что код не проверен. Не надо никаких хитрых псевдокодов - ты говоришь О Паскале, В разделе про Паскаль, С человеком, изучающим Паскаль, И, наконец, заключаешь все в паскалевские теги. И грубые ошибки (типа элемента массива в качестве параметра цикла) недопустимы в любом случае при объяснениях (говорю как администратор)).
valerosha
В условии ничего не сказано про вторую матрицу, так что речь скорее всего про ромб.
Всем спасибо за ответы! Просто супер! applause.gif
koda
А как на счет такой матрицы (условия задачи: Найти сумму элементов из области матрицы, отмеченной символом * (диагонали входят в выделенную область)smile.gif

* * * * * * *
0 * * * * * 0
0 0 * * * 0 0
0 0 0 * 0 0 0
0 0 * * * 0 0
0 * * * * * 0
* * * * * * *

тут походу точно должно быть две матрицы, или я ошибаюсь?
Помогите мне разобраться с такой задачкой.
volvo
Цитата
тут походу точно должно быть две матрицы, или я ошибаюсь?
И здесь все делается теми же двумя циклами:
  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
Почему то не получается, не могу разобраться, помогите. И в массив забивать можно любые числа или нет? К примеру:
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
Читать матрицу из файла не пробовал?

На данный момент все, что ты пытаешься сделать - это складывать нули, которыми матрица инициализируется при старте программы по умолчанию. Этого можешь не делать, я тебе и так скажу, ответ будет "0". Удивительно, правда?

К тому же ты еще и не выводишь ничего никуда, так что откуда ты вообще знаешь, получается у тебя что-то или нет? Телепатия?

Но самое главное - это сделать так, чтоб программа хотя бы откомпилировалась. Ошибки-то исправь, синтаксические. Где-то точку с запятой забыл, где-то еще что-то...

Цитата
Почему то не получается
Очень емкое описание ошибки. Хочешь получать такие же ответы? "Потому что внимательнее надо быть."

P.S. Сравни тот код, который привел я с тем, который привел ты. Как ты думаешь, какой проще читается? Выдели свой код тегами...
koda
Помогите мне добить этот пример, не могу сооброзить, что куда. Я ведь только учусь... буду очень благодарен.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.