Название: Вопросы по алгоритмам Отправлено: 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; 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; Ну а дальше, зная крайние индексы подматрицы с максимальной суммой элементов по периметру, уже не составит труда найти сумму элементов этой подматрицы. Желаю удачи ! :) ЗЫ: работоспособность кода я конечно же не проверял, но думаю логика программы правильная))) Название: Re: Вопросы по алгоритмам Отправлено: SPL от Январь 13, 2009, 12:14:24 Оргомное спасибо :) Разобрался, лаба сделана и работает, даже правильно :)
Название: Re: Вопросы по алгоритмам Отправлено: pfa от Январь 13, 2009, 01:05:50 Код: import java.util.Random; (Отправлено в: Январь 13, 2009, 00:01:16) Код: /** (Отправлено в: Январь 13, 2009, 00:02:37) Код: /** (Отправлено в: Январь 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> Код: А Название: 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. В итоге ты получишь общий масштаб для всех графиков. |