КИТА unofficial

Компьютерный => Программирование => Тема начата: SPL от Январь 12, 2009, 08:28:34



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


Название: Re: Вопросы по алгоритмам
Отправлено: Артем от Январь 12, 2009, 08:56:17
А подматрицы должны выделятся как на рис.1 или как на рис.2 ? Подматрицы тоже должны быть квадратными ?


Название: Re: Вопросы по алгоритмам
Отправлено: SPL от Январь 12, 2009, 09:21:48
Вершины должны лежать на диагонали и антидиагонали, т.е. как на рисунке 1, тоже должны быть квадратными)


Название: Re: Вопросы по алгоритмам
Отправлено: Артем от Январь 12, 2009, 10:40:56
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--;
}


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

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


Название: Re: Вопросы по алгоритмам
Отправлено: SPL от Январь 13, 2009, 12:14:24
Оргомное спасибо :) Разобрался, лаба сделана и работает, даже правильно :)


Название: Re: Вопросы по алгоритмам
Отправлено: pfa от Январь 13, 2009, 01:05:50
Код:
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 угла - достаточно и одного.


Название: Re: Вопросы по алгоритмам
Отправлено: Артем от Январь 13, 2009, 01:09:31
Думаю, очевидно, что решение уважаемого artem90 неоптимально хотя бы потому, что в силу граничных условий выделения подматриц нам не нужно хранить все 4 угла - достаточно и одного.
Да, действительно протупил :(


Название: Re: Вопросы по алгоритмам
Отправлено: Alder от Январь 13, 2009, 01:14:21
Off-Topic - помечено автором как "не соответствует обсуждаемой теме"
Форум глючит и не дает за раз отправить - сорри.
Проверил. Да, при постинге полного листинга анализатор тегов наверное где-то зацикливается. Если постить частями - нормально.


Название: Re: Вопросы по алгоритмам
Отправлено: ff000 от Январь 31, 2009, 10:00:39
Объясните пожалуйста зачем в решении снау в методы простых итераций нужна матрица якоби?


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


Название: Re: Вопросы по алгоритмам
Отправлено: ff000 от Февраль 01, 2009, 08:07:03
Постойте, у меня сходимость по k норме, и вычисляется она по простому(корень( (X1i-X1i-1)^2 +...+(Xni-Xni-1)^2) это никак не матрица якоби о_О , и до сих пор не понятно зачем матрица Якоби


Название: Re: Вопросы по алгоритмам
Отправлено: Артем от Февраль 01, 2009, 09:13:29
Объясните пожалуйста зачем в решении снау в методы простых итераций нужна матрица якоби?
Одмин, спасение лежит внутри :)
(http://i.piccy.info/i3/1d/d0/88c5a5eccdd96e484db3f0ebc710.jpeg)


Название: Re: Вопросы по алгоритмам
Отправлено: ff000 от Февраль 01, 2009, 09:39:48
ну а если я буду говорить касательно курсовой работы, и у меня нет перекомпеляции, и я руками посчитал производные и вписал в код, тогда мне не нужно будет вычисление матрицы якоби? и омя
да и че http://craft.nstu.ru/Labs/L10.pdf тут не сказано ничего про омя


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


Название: Re: Вопросы по алгоритмам
Отправлено: EvilMax от Февраль 01, 2009, 11:46:34
Думаю, обсуждение соответсвует теме, так как вопрос был по алгоритму.

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


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


Название: Re: Вопросы по алгоритмам
Отправлено: Артем от Май 31, 2009, 08:55:14
Archangel, выложи хотя бы часть кода.


Название: Re: Вопросы по алгоритмам
Отправлено: LazarusLong от Май 31, 2009, 09:41:37
Archangel, имхо, вопрос к С++ имеет мало отношения. Скорее вопрос по алгоритмизации считывания файла в utf-8. Причем тут С++?


Название: Re: Вопросы по алгоритмам
Отправлено: Archangel от Май 31, 2009, 09:50:41
Код простой:
Код:
#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 байта. Вот как их посчитать?


Название: Re: Вопросы по алгоритмам
Отправлено: Артем от Май 31, 2009, 10:35:45
Archangel, с utf-8, честно говоря, раньше дела не имел, поэтому может быть и глупость какую-то скажу, но все же))

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


Название: Re: Вопросы по алгоритмам
Отправлено: Archangel от Июнь 01, 2009, 07:50:33
Понятно в общем, надо что-то самому придумывать. Я надеялся честно говоря, на какие-то функции в с++ для работы с utf8.


Название: Re: Вопросы по алгоритмам
Отправлено: Магнетон Бора от Июнь 06, 2009, 06:32:10
Коллеги, подскажите кто-нибудь такую вещь. Я хочу в одной области построить несколько графиков функций, чтобы они все в этой области поместились, но масштабы у графиков разные получаются. Как мне построить все графики в данной области, при этом особо не исказив ничего. Я пробывал экспериментировать с масштабами и получилось, что все графики влезают в эту область, но есть недочеты. Например если f1 = 2 и f2 = 2, то на экране этого равенства не видно ((((


Название: Re: Вопросы по алгоритмам
Отправлено: Артем от Июнь 06, 2009, 06:44:53
Я хочу в одной области построить несколько графиков функций, чтобы они все в этой области поместились, но масштабы у графиков разные получаются.
Магнетон Бора, перебери массивы Y координат всех твоих графиков, и найди Ymin и Ymax. Потом таким же образом найди Xmin и Xmax. А потом относительно этого диапазона посчитай коэффициент масштабирования для осей X и Y. В итоге ты получишь общий масштаб для всех графиков.