Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ сумма элементов из области матрицы, отмеченной символом *

Автор: valerosha 15.10.2009 22:40

Здравствуйте,
подскажите, пожалуйста, решение или укажите нужное направление

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 раза меньше циклов

, а можно и совсем без циклов 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 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'ы, и можем читать не только строки, но и между)).
Ни о какой второй матрице - ни слова, а звездочками отмечен - ромб smile.gif.
Убедительная просьба мне не возражать прямо сейчас - давай дождемся автора темы, пусть он скажет.

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

Автор: valerosha 16.10.2009 14:03

В условии ничего не сказано про вторую матрицу, так что речь скорее всего про ромб.
Всем спасибо за ответы! Просто супер! applause.gif

Автор: koda 2.03.2010 13:36

А как на счет такой матрицы (условия задачи: Найти сумму элементов из области матрицы, отмеченной символом * (диагонали входят в выделенную область)smile.gif

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

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

Автор: 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

Помогите мне добить этот пример, не могу сооброзить, что куда. Я ведь только учусь... буду очень благодарен.