Для заданной матрицы размером 8 на 8 найти такие k, что k-я строка матрицы совпадает с k-м столбцом.
Найти сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент.

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

По всей проге вопрос такой: он мне считает все элементы начиная с 0 (как и полагается в массиве), но когда я пытаюсь сдвинуть цикл for (i=1; i=N-1; i++) всё рушится :(

И третий вопрос нафига тут flag? Без него прога не работала, я просто нагло скопировал часть с флагом и поэтому не врубаюсь фигли без него не работает.




Это сообщение отредактировал(а) Kruger2 - 30.6.2011, 14:13

flag надо инициализировать на каждом шаге цикла по i:


зачем?

Это сообщение отредактировал(а) baldina - 30.6.2011, 14:54

baldina
Начал писать и придумал как решить проблему  У меня ответы получались начиная от 0. Но в printf указать просто i + 1).

Инициализировал flag нулем, но ничего не изменилось. Всегда выдает, что есть совпадение в последней строке.

а в действительности нет совпадения?

Нет. Бывают совпадения в других строках. А последнюю выводит всегда, вне зависимости от того есть там совпадения или нет.

Добавлено @ 15:42
Вот блин, он мне и сложение не правильно дает, каждую строку после первой он начинает не с ноля, а с конечной суммы. Чорд чорд чорд)

Это сообщение отредактировал(а) Kruger2 - 30.6.2011, 15:43

посмотрите внимательнее. а лучше - задайте массивы вручную.
http://codepad.org/tMdEtddz

В условии же сказано о полном равенстве строки и столбца, верно? 

А у вас там в алгоритме выводится, что совпадение найдено, если есть хотя бы один такой элемент на позиции i,j, что симметричный ему элемент на j,i имеет то же значение... 

Попробуйте вот так, кажется, то, что нужно.


Это сообщение отредактировал(а) newbieone - 30.6.2011, 16:42

Всегда выдает: there is no equality =(

...на главной диагонали, i==j



Добавлено через 1 минуту и 55 секунд
это проверка совпадения хотябы одного элемента. если надо проверить все, то



Это сообщение отредактировал(а) baldina - 30.6.2011, 16:46

а для случайно сгенерированной матрицы у вас, собственно, никогда и не будет никакой equality. вы смотрите на свою матрицу, на первую строку, потом на первый столбец. все элементы в строке и столбце одинаковые? очевидно, при использовании rand() для заполнения массива - нет.

это вы откуда взяли про главную диагональ? там идет прогонка по всему массиву

Давайте для определенности N=8, i=1, j=0. Рассмотрим 4 строку:

Отнюдь не главная диагональ.

Это сообщение отредактировал(а) newbieone - 30.6.2011, 16:56

я имел в виду, что array[i][j] всегда ==array[j][i] при i==j

Добавлено через 53 секунды
именно поэтому у него всегда последняя строка попадает: там у последнего проверяемого элемента j==i и, соответственно, flag==1

Главная диагональ там играет роль именно только в последнем элементе последней строки.
На предыдущих же строках главная диагональ алгоритму Kruger2 вообще не важна: flag затирается при переходе от элемента к элементу, первые N-1 элементов могут быть различны, а N-тый элемент строки, в случае равенства N-тому элементу столбца, выставит flag в положение true, что якобы приводит к решению о равенстве строки и столбца (по сути, для положительного ответа программы у автора должны быть равны лишь A последних элементов строки и столбца, где A>=1 и не обязательно равно размеру строки/столбца N).

Ну всё просто, нужно обнулять ваш аккумулятор (sum) в начале каждого прохода по строке.

Это сообщение отредактировал(а) newbieone - 30.6.2011, 17:25

Видимо я не понимаю задания. У меня получается есть допустим массив:

1 1 1 1
1 2 3 4
1 3 3 2

Вот тут первая строка совпадет с первым столбцом и только такой выдаст нужный ответ?

Kruger2, внимательнее. В общем случае, если вы хотите, чтобы строка совпадала со столбцом, то количество элементов в них должно быть одинаковым (т.е. матрица должна быть квадратной). Иначе как вы, например, для вашего примера:

скажете, равен ли элемент [0][3]=1 элементу [3][0], если у вас четвертая строка отсутствует?
Если четвертую строку всё-таки добавить как-то так:
1 1 1 1
1 2 3 4
1 3 3 2
1 6 5 3
то, безусловно, ответом будет k=1 (т.е. только 1 строка и 1 столбец содержат одинаковые элементы).

Это сообщение отредактировал(а) newbieone - 30.6.2011, 18:00

newbieone, похоже, вы читаете невнимательно)))) долго объясняете то, что уже говорено

Ответ, зер из но иквилти. Что не так?)

baldina, возможно, между нами имело место быть недопонимание.
Kruger2, укажите номер k, для которого k-ая строка вашей матрицы содержит те же элементы (слева направо), что k-ый её столбец (сверху вниз). Я такого не вижу.

Не понимаю, где указать и что

Да здесь укажите, в виде ответа в теме   

У вас первая строка матрицы содержит те же элементы, что и второй её столбец. Это замечательно, но ваша формулировка задания требует:

То есть, номер строки и номер столбца должны быть одинаковыми. Вы можете сравнить 1 строку с 1 столбцом, 2ую строку со 2ым столбцом, но не можете сравнивать 1ю строку со 2 столбцом. Ферштейн?

ферштейн. убился об стену:(

Kruger2, так это же реализацию значительно упрощает.

Последний вопрос





Вот тут обнуляю сум. Всё стало работать норм кроме одного. Не считает последнюю строку, хотя там есть отрицательное число. Почему же он его не видит?:( Думал, может в последнем цикле фор должно <= но нет)


Добавлено через 1 минуту и 15 секунд
triclosan 
Конечно упрощает. Трудно решать задачу не понимая, чего от тебя хотят

Это сообщение отредактировал(а) Kruger2 - 30.6.2011, 18:21

Попробуйте, ответ должен быть: k=1, k=3.

По поводу второго задания: у вас в первой же строчке приведенного кода i должно меняться от 0 до N, а меняется до N-1, потому и нет последней строки.


Это сообщение отредактировал(а) newbieone - 30.6.2011, 18:44

Это сообщение отредактировал(а) voral - 30.6.2011, 18:50

newbieone 
Большой спасибо за помощь, разобрался и всё заработало. Плюсище от меня в репутацию поставьте человеку! =)
За код с подробными комментариями я бы вообще пивом угостил, если б мог. как правило приходиться голову ломать, что для чего) Реально большое спасибо.


voral 
Элегантно. Тоже спасибо, плюс в репу от меня!

baldina
Тоже спасибо, тоже плюсик

  

Kruger2, тебе до сотни постов немного осталось. сам и наплюсуешь 

Это сообщение отредактировал(а) borisbn - 30.6.2011, 19:13

borisbn, а это критично? Результаты будут верными и для вашего варианта, и для кода voral, а вот алгоритм - оптимальней ли?

Вне зависимости от знака элементов строки будут произведены N сравнений на равенство нулю, N обращений к элементу массива и проверок на отрицательность элемента, 1 присваивание. 2N+1 операция (или даже 3N+1, если обращение к элементу массива и сравнение считать двумя различными), если я нигде не наврал.
Теперь здесь:

В худшем случае, когда все элементы отрицательны, имеем N присваиваний и N сравнений. 2N операций (ну или 3N, при тех же условиях, что и выше). Всё, конечно, поменяется, если вы скажете, что операция присваивания требует больше ресурсов, чем операция сравнения, но намного ли? Надо еще учесть, что далеко не всегда будет худший вариант, возможно, только один из элементов будет отрицательным, тогда будем иметь всего N+1 (2N+1) операций против 2N+1 (или 3N+1 соответственно). Тогда исходный алгоритм будет требовать аж на N операций меньше, чем предложенный вами. 

UPD.: Хотя, если еще чуть подумать, можно вспомнить о short-circuiting, когда первое сравнение даст false и ничего больше вычисляться не будет...

В общем, всё это очень спорно   

Это сообщение отредактировал(а) newbieone - 30.6.2011, 19:50

Да нет. Тут все бесспорно. Поправка правильная. В любом случае если вызывает сомнение можно разложить этот if на два - и это будет шустрее чем мой вариант 

Тестировал для SIZE=15000, заполнение массива случайными числами.

It took: 15.312 seconds

It took: 16 seconds

Даже не знаю.

Это сообщение отредактировал(а) newbieone - 30.6.2011, 21:07

>It took: 15.312 seconds код
>It took: 16 seconds
IMHO всего на 15000 7%  выиграша уже не плохо

Если это кому-нить нужно , ессно

Не совсем правильное сравнение. Тут основное время занимает заполнение массива. Вот я почистил код. Каждый вариант запускается по три раза:

В результате у меня получися следующий вывод:

А если как-то так попробовать?



Это сообщение отредактировал(а) Dov - 1.7.2011, 00:10

Да это будет быстрее. 

Это сообщение отредактировал(а) voral - 1.7.2011, 00:38

Окей, практика показала увеличение производительности. А теперь теоретически это как-то можно объяснить? Я вот на прошлой странице пытался провести сравнение сложности алгоритмов "на бумажке" по количеству машинных операций, но, видимо, оно чего-то (многого) не учитывает.

Это сообщение отредактировал(а) newbieone - 1.7.2011, 09:47

Это о последнем алгоритме?
Там все просто. 
Сначала бежим по каждому элементу сторки, прибавляем его у сумме и сравниваем.
Как только нашли первый отрицательный элемент, нас уже не интересует есть ли еще отрицательные, по этому мы уходим в продолжение цикла где нет проверок на отрицательность, т.е. избавляемся от лишнй операции на каждую итерацию. (в предыдущем "быстром" варианте мы все равно проверяли флаг на равенство 1 или 0)

voral, я имел ввиду математическое пояснение в терминах теории сложности вычислений (сложности алгоритмов).

Вашего первоначального и того, что предложил borisbn.

Это сообщение отредактировал(а) newbieone - 1.7.2011, 10:26

а вы про этот пост где N расписывали 
Ну тогда както так:
В худшем случае (кагда нет отрицательных числ)
мы имеем N сравнений и ни одногоприсваивания
В лучшем случае когда первый элемент в строке отрицателен имеем 1 сравнени и так же ни одного присваивания.

Итак имеем от 1 до N (в зависимости от позиции отрицательного числа) операций против от N до 2N

Добавлено через 4 минуты и 35 секунд
А вообще. Если целью поставить быстродействие и если позволяет процедура заполнения матрицы. Добавить еще один одномерный массив. При вводе нового элемента матрицы анализировать существование отрицательного значения и заносить номер строки в массив. Хотя в этом случае (такой ввод) моно собственну и суму здесь же считать. Но это уже теряем гибкость.

voral, не могу с вами согласиться. У вас же там в условном операторе два условия через &&, сравнений соответственно будет в два раза больше, плюс вы забываете о сравнениях (о первом из них, второе из-за short-circuiting не будет вычисляться) уже после присваивания...
Если пытаться анализировать этим способом, имеем практически одинаковые результаты: N+2 до 2N против N+1 до 2N.

Если первый элемент отрицательней, проведется 2 сравнения, 1 присваивание, и после этого еще N-1 сравнений (т.к. fexists станет равным единице, то первое сравнение даст false и дальше выражение вычисляться не будет). В сумме N+1 сравнений и 1 присваивание, т.е. N+2 операций.
Если все положительные, то fexists всегда остается равным нулю и имеем 2N сравнений.

Здесь если существует единственный отрицательный элемент, N сравнений и 1 присваивание, т.е. N+1 операция.
Если все отрицательные, N сравнений и N присваиваний, т.е. 2N операций.

Другое дело, что способ, судя по практическим результатам, не совсем верен. Практика с теорией расходятся...

Это сообщение отредактировал(а) newbieone - 1.7.2011, 13:50

видимо мы о разном. Я разложил именно поселедний самый шустрый вариант.
Этот же случай 

я понимаю так. 
Самое плохое когда нет отрицательных
два сравнения, сложение энд т.е. 3N - операций 
Самое хорошее когда первое отрицательное
первая итерация  два сравнения, сложение энд и присваивание 4 операции
остальные итерации одно сравнение
т.е. (N-1)+4
Т.е получаем от N+3 до 3N  против N+1 до 2N, (кстати операция операции рознь и && совсем не одно и то же что сравнение)

К тому же. У нас диапазон чисел от -1 до 9. При размере матрицы 15000 шанс что в строке не будет отрицательных чисел очень мал. Т.е. скорее всего исходный случай с одним сравнением будет стремиться именно к 2N, В то время как где два сравнения врят ли дотянет до 3N...
Думаю если уменьшить размер, или увеличить диапазон чисел.... ТО может быть преимущество перейдет.

Это конечно все просто рассуждения можно попробовать посмотреть на практике. Дизасемблировать оба варианта, чтоб посмотреть как это выглядит на асме; и сделать с промежуточным выводом значений... 

Хехе, ну вот, а говорили на предыдущей странице, что

Вот еще небольшой тестик

Результат:


Добавлено через 2 минуты и 54 секунды
При размере строки 11 все равно неплохой результат:

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

Тут я взял за основу код уважаемого voral, т.к. удобнее дописать функцию

вот основа:




Вот что я добавил: 





Значит функция maloc вроде бы написана без синтаксических ошибок, ибо компилятор не матерится. Однако как проверить правильно ли выделяется память я не знаю, поэтому прошу провеhить код функции maloc

Далее, то что код функции freememory должен находится не тут я понимаю (ибо выделил память и тут же аннулировал), но где она должна находиться? После main? прямо перед main? Будьте добры, подскажите.

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

Ты сделал свои обертки для malloc и free.  Желательно их вызывать (для одной области) в  рамках однной функции - в которой живет переменная хранящая адрес.

Однако, могут быть ситуации когда ты передаешь адрес в другую функцию/поток, а из той в которой создал уходишь... Тогда уже там надо позаботиться об освобождении.
Например

Переменная Result будет уничтожена. Но память останется выделенной.....

Т.е. мне надо вызвать функцию малок внутри каждой из моих двух функций или вызвать её в мейне перед выполнением двух других функций?

Добавлено @ 14:40
и получается освобождать память тоже не надо, т.к. нет глобальных переменных ?

Это сообщение отредактировал(а) Kruger2 - 11.7.2011, 14:40

Вызываю внутри каждой функции сначала inmemory, затем freememory (решил переименовать малок в инмемори, что бы внести ясность)

Это сообщение отредактировал(а) Kruger2 - 11.7.2011, 14:53

сделав обертки, мы получили те же самые malloc и free, концептуально ничего нового.
в вопросах управления ресурсами, в т.ч. памятью, важно понятие владельца. именно владелец отвечает за своевременное удаление объекта (освобождение ресурса). выделение ресурса может происходить вне владельца, важно, что бы сразу после выделения установить владельца.
на примере умных указателей:

здесь выделение ресурса происходит вне владельца - переменной my_ptr, но владелец устанавливается сразу. освобождение памяти произойдет, кода закончится время жизни my_ptr. если между выделением ресурса и установкой владельца что-то происходит

есть вероятность возникновения исключения, тогда память не будет освобождена.

   В общих чертах я это понимаю. Теорию из книги прочитал, теперь пытаюсь перенести теорию на практику. 
   Если я вас правильно понял, мне не нужно освобождать память по окончанию выполнения функции, т.к. локальная переменная сама сотрется при выходе из функции? 

   Хорошо, тогда правильно ли я вызываю функцию динамического распределения памяти? Внутри функции, которая оперирует интересующими меня переменными я вызываю функцию выделения памяти, т.е. всё верно? Потому что я сомневался, может я в мейне должен вызвать функцию malloc(inMemory) перед началом выполнения двух других функций, но это получается нелогичным, т.к. память выделиться на все последующие функции и захламится мусором этих самых функций и при этом не произойдет очистки памяти. Верно?

Kruger2, тут какая-то каша в коде.
давай вернемся к задаче. требуется написать управление памятью и доступом для квадратной матрицы.
определим операции
1. создать матрицу порядка N
2. получить доступ (для чтения или установки значения) к элементу (i,j) матрицы
3. освободить занимаемую матрицей память

пусть у нас будет

предлагаю структуру сделать такой:

тогда data должен указывать на память размером size*size, а элемент (i,j) в data находится по индексу i*size+j
остальное, думаю, сам реализуешь.
ЗЫ: с использованием классов это можно сделать намного изящнее

Добавлено через 3 минуты и 14 секунд

совсем не вызываешь

это не вызов, а объявление

Это зря, структуры не изучал ещё.

Совершенно непонял


Матрица у меня уже есть, зачем мне её ещё раз создавать, зачем мне функция получения значения элемента?

Брр, стало только хуже. Я хоть немного понимал, что я и как делаю. У меня была задача состоящая из двух функций, по идее мне достаточно было выделить память под эти две функции, что бы решить новое задание. Но теперь весь код каша? А в каком месте то каша? сейчас есть 4 функции, 2 из них решают основное задание, а 2 другие это выделение памяти и очистка. Вроде до каши ещё далеко   

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


Добавлено через 4 минуты и 52 секунды

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

1. вместо структуры будем использовать две переменные - указатель на выделяемую память и порядок матрицы.
я предлагаю использовать одномерный массив для матрицы. это гораздо проще в выделении памяти, а лдя доступа будем использовать очень простую функцию

Это сообщение отредактировал(а) baldina - 11.7.2011, 15:27

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


Мда, тут вызвать никак не получается 

При попытке вызвать функцию посредством

 inMemory (b) пишет   expected primary-expression before ')' token, 
что за праймери экспрешен?(

посмотри что получилось: теперь все операции с матрицей мы можем осуществлять через эти (очень простые) функции.
можешь добавить проверки выхода индексов за границы.
можешь добавить отладочную печать.
на вызывающий код это не повлияет.

Добавлено через 1 минуту и 28 секунд

ну вообще-то у тебя в программе b определена как int, а inMemory требует int**

даже функцию блин вызвать не могу)

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

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

Меня интересует в первую очередь два вопроса. Верны ли сами функции inMemory и freeMemory и будет ли верным такой вызов?



Добавлено через 1 минуту и 59 секунд
baldina, 
Да я вроде литературу читаю, простые задачи решаю, но как то ориентироваться лучше не начинаю. Хоть бери об стенку убейся, как только появляется задание выходящее за рамки того что описано в книге, я словно пытаюсь по китайски заговорить:*(

Добавлено через 6 минут и 14 секунд
Вообщем то тоже неверно, программа рушится

Добавлено через 7 минут и 59 секунд

Но у меня то двумерная матрица

Добавлено через 14 минут и 34 секунды
Ладно. Пробую разобраться:



get_m помоему все таки лишняя, разве нет? у меня ведь объявлена матрица, получается я работаю не с ней, а с той что тут будет создана
void_st //функция установки значения элемента, вообще не понимаю что за установка значения. мы же не рандомную матрицу создаем.
create matrix создает одномерный массив, тут кажись вся моя функция с проверкой должна подходить, нет? 


а destroy_matrix вроде как должна подходить моя же функция?

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

по порядку.
1. что такое многомерный массив в С/С++? это одномерный массив, строки которого расположены последовательно в памяти (ничего необычного, ведь компьютерная память одномерная). Именно такое расположение я и предлагаю. Это проще для восприятия, чем "массив массивов".
2. неважно, что как расположено. мы пользуемся определенным интерфейсом - функциями create, get, set... Этот подход нам позволяет в процессе решения конкретной задачи не вникать в устройство массива, а в процессе проектирования интерфейсных функций не думать о всей задаче. поэтому get_m не лишняя. технически можно без нее обойтись, можно вообще все написать в единственной функции и в одну строчку, но с точки зрения грамотного проектирования и удобства использования она нужна.
3. 

ну поскольку она в итоге вызывает тот же malloc, то примерно да. точнее, если взять мою функцию и добавить туда проверки и сообщения, будет 'правильная' версия Kruger2
теперь рассмотрим 

здесь есть две основные проблемы
1. параметры в С/С++ передаются по значению, поэтому если нужно инициализировать int**, то передавать приходится int***

2. К выделенному таким образом массиву нельзя обращаться A[i][j], т.к. элементы массива теперь не расположены последовательно.
нужно так: (A[i])[j];
уже не так красиво, как раньше, правда?  

Всё равно ни черта не понимаю. Пойду ещё искать литературу.

Добавлено через 7 минут и 24 секунды
Вот я копировал отсюда, немнго меняя под себя. получается тут неправильный код выложили?)

Kruger2, есть простой выход. вообще он не очень хороший, но в данном случае наверно лучший.
сделай 
и обращайся A[i][j] Более сложное попробуешь, когда почитаешь

так?

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

Во вторых у вас все неправильно. Давайте прочитаем по русски этот код:

обявляем две переменные типа int.
пытаемся объявить (не вызвать) функцию, которая в качестве аргумента принимает указатель на указатель на переменную типа int
пытаемся объявить (не вызвать) функцию, которая в качестве аргумента принимает указатель на указатель на переменную типа int

Все не более.
Отбрасываем ошибку, с попыткой объявить функцию

Опять не увязка:
1 ваша процедура ждет указатель на указатуль......
2 Места для переменных типа int уже зарезервированы, и нет смысла выделять память (а еслибы все же нужно было то надо было писать "&b"
Правим

Теперь все, вроде так. Но! Вызывая inMemory(b) ; вы в конечном итоге инициализируете переменную b, адресом массива указателй
переменная c при этом неинициализирована! А вы хотите освободить память по адресу хранящемуся в этой переменной!!! Ноона ни чего не содержит!
Еще раз правим.


Вот теперь вы память выделили, а потом освободили. Осталось придумать зачем она вам тут сдалась... В данной задаче единственное применение для этих функций. Зарезервировать место под матрицу; заполнить ее программно (сейчас у нас это константа); найти решение; освободить память.. Т.е. по сути, это должно быть в main



Если вы где то зарезервировали память, то вы обязаны ее освободить - иначе "утечка памяти". То, о чем я вам говори касается лишь освобождения памяти под автоматическую переменную хранящую адрес выделенной вами памяти.

Это сообщение отредактировал(а) voral - 11.7.2011, 17:34

смотрите сами: http://codepad.org/KAP0hVsz

voral, 



При вызове функции freeMemory программа рушится.

Добавлено через 1 минуту и 29 секунд
baldina, 
Посмотрел, код рабочий. Следовательно у меня вызов кривой.

Добавлено через 2 минуты и 28 секунд
Но нет освобождения памяти. И в примере выше при попытке высвободить память программа рушится.

На всякий случай

Самое обидное что в книге кернигана и ричи 2 строки по динамическому распределению памяти, а у харви дейтела "как програмировать на си" вообще ничего)

Судя по содержанию вспоминают они о нем только в структурах

плохо смотрели. не годный код.

тут и я немного прощелкал. Дело в том как передан параметр в inMemory. Пока сам руками не написал не осознал . Объяснять времени не осталось, вот то что я написал