Вопросы по алгоритмам

[SPL]

Здравствуйте) Уже довольно долго не могу сдать лабу из-за того что не получается выполнить задание) В моей программе (на Си) необходимо написать функцию, которая определяет сумму всех элементов подматрицы с большей суммой элементов на периметре. Матрица квадратная, динамическая.
Никак не могу придумать алгоритм. Мб у кого-то есть идеи - буду благодарен)

[Артем]

А подматрицы должны выделятся как на рис.1 или как на рис.2 ? Подматрицы тоже должны быть квадратными ?

[SPL]

Вершины должны лежать на диагонали и антидиагонали, т.е. как на рисунке 1, тоже должны быть квадратными)

[Артем]

1) Определяем сколько у нас должно быть подматриц:

2x2, 3x3 - 1 подматрица
4x4, 5x5 - 2 п.
6x6, 7x7 - 3 п.

Код:

int size, submatrix;
// ввод размерности матрицы и выделение памяти
submatrix = size / 2; // дробная часть если и будет, то отбросится и получится целое кол-во подматриц

2) Для того чтобы выделять подматрицы введем переменные, которые будут хранить индексы по периметру:

Код:

int left, top, right, bottom;

Также введем переменные, которые будут хранить индексы для подматрицы с максимальной суммой элементов по периметру:

Код:

int max_left, max_top, max_right, max_bottom;

3) Ищем подматрицу с максимальной суммой элементов по периметру. В коде нужно будет использовать индексацию массива через указатель *(A+i*n+j), так как память выделялась через одинарный указатель и обычная индексация A[ i ][ j ] вызовет ошибку компиляции. Но для лучшей читабельности кода и поонятности алгоритма, я решил оставить вариант с A[ i ][ j ].

Код:

int i, j, sub, sum, max_sum = -1000;
max_left = left = 0;
max_top = top = 0;
max_right = right = size-1;
max_bottom = bottom = size-1;

for(sub=0; sub<submatrix; sub++)
{
   sum = 0;
   for(i=top; i<=bottom; i++)
      sum += a[i][left] + a[i][right];
   for(i=left+1; i<right; i++)
      sum += a[top][i] + a[bottom][i];  
   
   if(sum > max_sum)
   {
      max_left = left;
      max_top = top;
      max_right = right;
      max_bottom = bottom;
      max_sum = sum;
   }   
   left ++;
   top++;
   right--;
   bottom--;
}

Ну а дальше, зная крайние индексы подматрицы с максимальной суммой элементов по периметру, уже не составит труда найти сумму элементов этой подматрицы. Желаю удачи !

ЗЫ: работоспособность кода я конечно же  не проверял, но думаю логика программы правильная)))

[SPL]

Оргомное спасибо Разобрался, лаба сделана и работает, даже правильно

[pfa]

Код:

import java.util.Random;

/**
 * Created by IntelliJ IDEA.
 * User: pfa
 * Date: 12.01.2009
 * Time: 21:28:38
 * To change this template use File | Settings | File Templates.
 */
public class MatrixFinder {
    public static final int n = 6;
    private static int matrix[][] = new int[n][n];

    /**
     * Заполняем случайно, коэффициент криво взвешен для того, чтобы максимальная сумма
     * была не у внешнего периметра исходной матрицы
     */
    private static void initMatrix() {
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int randNum = n * 10 / ((Math.abs(n / 2 - i) + Math.abs(n / 2 - j) + 1));
                matrix[i][j] = rand.nextInt(randNum);
            }
        }
    }

(Отправлено в: Январь 13, 2009, 00:01:16)
 

Код:

    /**
     * Вывести матрицу на стандартный вывод
     */
    private static void printMatrix() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.format("%02d ", matrix[i][j]);
            }
            System.out.println("");
        }
    }

    /**
     * Считает сумму ряда от элемента startColumn до (размер-startColumn)
     * @param rowNumber номер ряда, который суммируем
     * @param startColumn начальный столбец
     * @return сумму
     */
    private static int countRowSum(int rowNumber, int startColumn) {
        int sum = 0;
        for (int i = startColumn; i < n - startColumn; i++) {
            sum += matrix[rowNumber][i];
        }
        return sum;
    }

    /**
     * Считает сумму элементов на периметре заданной подматрицы
     * @param submatrixNumber номер подматрицы от 0
     * @return сумму
     */
    private static int countPerimeterSum(int submatrixNumber) {
        int sum = 0;
        final int endElement = n - submatrixNumber-1;
        sum += countRowSum(submatrixNumber, submatrixNumber);
        sum += countRowSum(endElement, submatrixNumber);
        for (int i = submatrixNumber+1; i < endElement; i++) {
            sum += matrix[i][submatrixNumber];
            sum += matrix[i][endElement];
        }

        return sum;
    }

(Отправлено в: Январь 13, 2009, 00:02:37)
 

Код:

    /**
     * Ищет номер подматрицы с максимальной суммой элементов на периметре
     * @return
     */
    private static int findMaxSubmatrix() {
        int maxSum = 0;
        int maxNumber = -1;
        for (int i = 0; i <= n / 2; i++) {
            int curSum;
            if (i == n / 2 && n % 2 == 1) {
                curSum = matrix[i][i];
            } else {
                curSum = countPerimeterSum(i);
            }
            System.out.println("i=" + i + " sum=" + curSum);
            if (curSum > maxSum) {
                maxSum = curSum;
                maxNumber = i;
            }
        }
        System.out.println("Max sum: " + maxSum);
        return maxNumber;
    }

    /**
     * Считает сумму всех элементов подматрицы
     * @param maxSubmatrixNum номер подматрицы
     * @return
     */
    private static int countSubmatrixSum(int maxSubmatrixNum) {
        int sum = 0;
        for (int i = maxSubmatrixNum; i < n - maxSubmatrixNum; i++) {
            sum += countRowSum(i, maxSubmatrixNum);
        }
        return sum;
    }

    public static void main(String[] args) {
        initMatrix();
        printMatrix();
        int maxSubmatrixNum = findMaxSubmatrix();
        int result = countSubmatrixSum(maxSubmatrixNum);
        System.out.println("Result: " + result);
    }
}

(Отправлено в: Январь 13, 2009, 00:02:53)
 Форум глючит и не дает за раз отправить - сорри.
(Отправлено в: Январь 13, 2009, 00:03:12)
 Ах, да. Думаю, очевидно, что решение уважаемого artem90 неоптимально хотя бы потому, что в силу граничных условий выделения подматриц нам не нужно хранить все 4 угла - достаточно и одного.

[Артем]

Думаю, очевидно, что решение уважаемого artem90 неоптимально хотя бы потому, что в силу граничных условий выделения подматриц нам не нужно хранить все 4 угла - достаточно и одного.

Да, действительно протупил

[Alder]

Форум глючит и не дает за раз отправить - сорри.

Проверил. Да, при постинге полного листинга анализатор тегов наверное где-то зацикливается. Если постить частями - нормально.

[ff000]

Объясните пожалуйста зачем в решении снау в методы простых итераций нужна матрица якоби?

[EvilMax]

По-идее, при решении не нужна. Метод похож на метод решения одного уравнения, т.е. фактически идут последовательные приближения. Но есть нюанс. Сходимость решения проверяется по максимальному по модулю знаению частной производной fk по xi. Но так как для этого необходимо вычислить все частные производные, то это фактически эквивалентно расчёту Якобиана.

[ff000]

Постойте, у меня сходимость по k норме, и вычисляется она по простому(корень( (X1i-X1i-1)^2 +...+(Xni-Xni-1)^2) это никак не матрица якоби о_О , и до сих пор не понятно зачем матрица Якоби

[Артем]

Объясните пожалуйста зачем в решении снау в методы простых итераций нужна матрица якоби?

Одмин, спасение лежит внутри

[ff000]

ну а если я буду говорить касательно курсовой работы, и у меня нет перекомпеляции, и я руками посчитал производные и вписал в код, тогда мне не нужно будет вычисление матрицы якоби? и омя
да и че http://craft.nstu.ru/Labs/L10.pdf тут не сказано ничего про омя

[Polyakov]

Г-н FF000 я что-то не понял почему в теме «Вопросы по алгоритмам» весь форум должен обсуждать Вашу курсовую работу? Заметьте не алгоритмы, а именно задание Вашей к/р в том понимании, которое Вы сами себе представили, в некоторых случаях даже не прочитавши задание?
Но если же и обсуждать Вашу работу, то для начало сообщите как Вы ходили на консультации? Когда первый раз Вашу работу увидел преподаватель? Когда Вы первый раз принесли ее на сдачу?
И вообще выведите обсуждение работ в отдельную тематику.

[EvilMax]

Думаю, обсуждение соответсвует теме, так как вопрос был по алгоритму.

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

[Archangel]

такой вот вопросец в с++:
Решил сделать простейшую операцию, считать файл. Потом посмотрел что считалось, вроде все норм, потом пытаюсь, выковырять некоторые символы, и начинается паника - видим кракозябры. Пошевелив мозгами, видим что кракозябры знакомые, быстро смекаем что виной всему грозный utf8, отщепнув от русской буквы один байт видим естественно кракозябр. Ну да ладно, думаю помножим на два и фиг с ним, а не тут то было, ведь есть еще знаки препинания, которые занимают всего 1 байт. И скажите пожалуйста как с этим можно нормально работать?

[Артем]

Archangel, выложи хотя бы часть кода.

[LazarusLong]

Archangel, имхо, вопрос к С++ имеет мало отношения. Скорее вопрос по алгоритмизации считывания файла в utf-8. Причем тут С++?

[Archangel]

Код простой:

Код:

#include<iostream>
#include<fstream>

using namespace std;

main ()
{ 
  string text1;
  ifstream file1("CText10.txt");
  file1 >> text1;  
  cout << text1[18] << text1[19] << endl;
  cout << text1[20] << endl;
  cout << text1[21] << text1[22] << endl;
  cout << text1;
  return 0;
}

Результат:

Код:

А              
.              
Ч
ТФИОМОЛЗЪА.Ч:УЕЛL-РЖХЩБЦЦ.Р?ЯУСИИЯЙУЛЯЦ;ЛL;,МГ!БЦЦ.ЖЭ,НЛL!ВМЯХТЫБПОИШМЦТУДРУФХ;МЛИТЩБФ:ИЫБУ?ЦЫБ:L;;ВООЬО;ДLЦОНЮL;ЬЕ.Р:;ЗИИЯ,НЛL,_ПДLЪХВИМТ_Э.ИЧЯОЦЮЧШ;КФЯ_ЙНЖЮЦА.З_ЫОЮL.ДЕИШДЪЙ.ИИЪБХЦ_ЯТНОRДЛСЧ!ВНЪОЬОЦВL.ШФЪЖЖRЖЖФИРЙЗЖИЪПОФЦ,Ж.СЖТЙ.ИИЪПЗУГ.;ЫЛФЦПХФФ,Ц.ЧЖЮУЦРТ.;ООУЬ;ЕLЬЬССШЬЦЦ.УТДБРЙЭЦКФРЪЧ;ПЖЯУС.ХЪТЗГРТ.!.УЪ?УСLЯУ;ТЦЧТГИЯТЩП.УЧЭСЛ?!ЫПФШЧЧА.ИИРПКК?.ЖВLЯОРССЯУОРФЮДБУФЮОУГТЪДИУЛЭЬКВL?РЖУЛЯЫПМLФУТР;СДСГНЭЦГГСЪЯЭ.СЧЫЙЕФЧДЕСИ_ЩЭФШФЬ;ЛL__СГКЯО_.ЧЬ;ЛГ,ИЯПОУ-У;ТЦЪЭЖНЖЭЬ;РЛИЫБ.Ю?_ЛЦЕИЦ;ФРТЪЖМРЪН;ЪШ_ДПНЖЩОМЛЧДДГ.ШЧЫЙВLФЯЖ.ЗГЩЙ.НТЫ_Х;ЛДОГL_ТОСПИЦИ.УЪ.А.ЦТЯРСС_ФЖРУ_Ч;РЛ;ЬЕГСЧШФ.Ф!ДДУФ!О;ЛL_ПСГЯЧЫОСПИШ;УЛАУУНЛСДИГLЬЬУСЦ_Ч;РЖ,ЦОГСТЯЭ.УЧСМЛУЯО_.ЩЭЦЧГLЪДГЛКЯУМГЧДДЗИС!О_.Ч!УОГLЮООИМТН;ФОЦУМЛLЦРЖ.КТЪЬLL_ТОГЕИЯПЕЧЧЪ;;УТГ;ТФШОМЦПСДШХФИЦ;РЛИТБПЖИРПЕЧЧН;ГLУОСЮЮЯГ;ЪО!ОМГLЬЫЙЙР?ДГ.ЧТ:Э:У_РППL;УСИХЭУУИЕИ_П.ОИТЖОФИЯ;УЖ.ЯЖ:УЯ,Н.СЖППТ;!ЯУЕФЮДРСЙЭГЕЮИТГ;ТФИЯУСЦ_ЫБП,ИРУСЦТГА.Й_ЮБКК_ДТХЖ:LЖВLФДЕСЗ:ЬУРФЮДУИТЯЬ,ФОЯУН.ЮЧЮТХ?ЯЬН.ХЭОУЯЛИЦ;ТЦТШУЛЭЯ,Ц.З__ЙНЖRДОГLАЫФУФФШЖВL.ЬТУЛЦЬУСЭЧЫОСLФГИГСТДОИЭ!Ь;:К_РЙХФ:ЬИСИ_УА.ТЧЮОСL;УСИЗЪЮБ:L.ЭЙЩЖЮЦ!.Х:Ц;_Ш_Ъ;СУТДФФХЧРБОЖИРЖУШЧ_Э.Й_ЩПЕФЫДУСLФЭСГИ_Н;ХФИРМИИ_Н;ЛLЧУ;Д;._СЮПИРИЖСЗТ;Д;ЭДЕСL!ЬДСL-УРНОЮН;ЪШ_Н;ЕЛ:ЫПВL__;РЛХЬ;РОЬОЛ.УЧДНСЙЭЬ;ЦЧЬЬМЯНЯ;УЯL,_ПБУЪПФЗ:И.ПХ:ИЯЛССДШПБШ_ДРУОЮУШГШЧЩЭРФЧЗ;РЖИЪПОФЦЬДСL,УМСИЧШБ.ИИ;ИНОRДЛОЛ!?БХ;RДРГУ!ОМСУТ.А.ЧЖЮУЦРЧН;РЛУЮЖЙУ_ДСГЧ._ЖЖУ?_ППLЯОЕ.ЗЧЩЬПLШЦМИШ_ЪА.ОИШСЦЙЭЬК.ЮФУКЩЖ:ЯЛСПИLМ:ХЧДЕГТТДПДЦТ_ЙОЖИРОЛТТЫЙИL.ЮБКЩИ;З.З_ЩЭРФИЯУУЖЯЫП.ЮЧЩ;СУИЭП.ЖЭЩЖИ-И_П.Ф._БРФФЦУФ?СДГЮЧЮОУУОФО_.Р_СПБШ_ДТУЛЦЦ;ЖЩЭГЯЬОRН;ХФИЭПУ;ФЦТХФИЯЕИСТУУ.УЧЯЛССДШП.ЮТСПЕЕИ_П.ЧЯЬГГLЩОТХ;ЯУУLLФЫЖКЖ;ЫП.УЧ;СГИЯЬГИЮЧЫОЮПИЯФД_ЧШУ.ИЩСМ:У?Щ;РЖИЫБЫОRДЕГТИЦА.ЧЭЬГРФИЭСЛУЗР;РЛЬЬЖ.ЦЧLЖРОЧН;РЖ;ЮБЕОЭЯ_.РИЫЙПLАЦССРЪЪЙ.ЮТСБПОЛДПФШТЫПЕОЭЯ_.ХЧЮЖЗL.ШБПЛЫШПМLЪН;СЗ:ОЪГ?.А;НLЖЫПМLУОСЮЮЯУА.И_ЯЛООЬЫФОLА;УСИ.ШЙПLLОМЯЬЧ_ПП-К

Собственно надо посчитать число символов. С однобайтной кодировкой - без вопросов бери да считай. А тут "А" - 2 байта, "." - 1 байт, "Ч" - 2 байта. Вот как их посчитать?

[Артем]

Archangel, с utf-8, честно говоря, раньше дела не имел, поэтому может быть и глупость какую-то скажу, но все же))

Прочитал в Вики, что первый байт всегда имеет вид 11xxxxxx, а остальные — 10xxxxxx. Идея в том, чтобы брать по байту и проверять с помощью побитовой операции "И" значение предпоследнего разряда. То есть, взяли мы, например, первый байт русской буквы "А", у него предпоследний разярд всегда будет 1. Дальше считали след байт, проверили, у него предпоследний разярд - 0. Вывод - это символ занимающий 2 байта. Потом считали первый байт символа ".", у него тоже предпоследний разряд всегда - 1. Идем дальше, считываем след. байт, у него предпосл. разряд - тоже 1. Вывод - это уже пошел первый байт СЛЕДУЮЩЕГО символа. А это значит, что текущий символ занимает 1 байт, то есть он является либо символом латинского алфавита, либо знаком препинания или же управляющим символом из ASCII таблицы.