Изпечатай

[borovaka]

Здрасти,
Някой сеща ли се за решение на следната задача:
Да се напише програма която въвежда матрица с максимален брой редове 1000 и максимален брой стълбове 100. След въвеждането на матрицата да се изведе поредният номер на стълба в който произведението на всички негови елементи е най-голямо.
За целта не може да се ползват допълнителни библиотеки.

Някой ако има желание да опише някой алогритъм ще съм благодарен.

[b2l]

Dynamic Allocation of Arrays

E, имаш и една проверка за броя на редовете и стълбовете (редовете да не е по-голям от 1000 и стълбовете да не са повече от 100). Останалите неща са тривиални. Събираш, проверяваш и принтираш.

[borovaka]

Е то това ясно де проблема е как ще се умножат 1000 числа в смисъл long няма да може да хване резултата, щото това може да са числа от порядъка на 9999999 * 99999999 и т.н.
Обясниха ми го, че става с разпадане на числата с число на степен * число на степен и т.н. и сравнение. Интересно ми е има ли и други методи.

[b2l]

Интересно - не се бях замислил, и като попаднеш на някое Марсеново число какво правим?

[borovaka]

Ами аз нямам представа решение конкретно не съм виждал.
А това число какво е в смисъл просто число? Зле съм с математиката.

[b2l]

Ами аз нямам представа решение конкретно не съм виждал.
А това число какво е в смисъл просто число? Зле съм с математиката.

Ако задачата ти е поставена от училище или университет - просто ги пишеш long и после алгоритъма ти е ясен, ще пишеш по-малки чиска, а те даскалите като ги знам какви са това изобщо няма да го вземат в предвид.

[borovaka]

Задачата е от състезание по информатика.
Иначе ето за това представяне на числото говоря:
цък

[b2l]

Задачата е от състезание по информатика.
Иначе ето за това представяне на числото говоря:
цък

Ми хубуу де, значи хващаш числото в (1,1) и започваш да го делиш. Делиш го първо на 2, докато има остатък 0, после на 3, на 5...
Само дето не знам после какво ще го праиш като си го разделил на множители.

[romeo_ninov]

Задачата е от състезание по информатика.
Иначе ето за това представяне на числото говоря:
цък

Ако можеш да ползва логаритъм го ползвай, и събирай логаритми, така можеш да работиш с много по-големи числа (макар и с грешка)

[bvbfan]

Като цяло задачата изисква почти никакви познания по С, а по Висша Математика. В Университета не сте ли учили матрици и детерминанти. С всякакво вид делене резултатът ще бъде с приближение и е възможно в зависимост от числата процента грешка да варира в голям диапазон. Трябва да се разбият на матрици алгоритъм на Bareiss.
ПС: Учил съм го, но не мога да го приложа, свързано със сивото вещество, при мен липсва 

[gat3way]

Не е много сложно да се напишат функции, които работят с големи числа, представят се като низове. Това е при положение че има само събиране, изваждане и умножение. Деленето и намирането на остатъци е много по-крива работа.

[arda_kj]

@borovaka - romeo_ninov ти подсказа да използваш логаритми, какво по-просто от това. Така може да работиш с огромни числа и така вместо умножение ще имаш събиране на логаритми. Естествено първо конвертираш числата във floating point формат, след това използваш десетичен логаритъм, например:

log10(a13*a23*...*an3)=log10(a13) + log10(a23)+...+log10(an3)

a13, a23,..., an3 са елементите от 3-тата колона. Както виждаш при логаритъма умножението на числата от колоната се разлага на събиране на техните логаритми, което ще даде много по-малко число следователно си решаваш проблема с range-a.

Сега ако не може да използваш и math библиотеката, вече не знам, ще трябва ти да си пишеш алгоритъма за смятането на логаритмичната функция, ама това не е нещо сложно.

Освен това до тук условието на задачата е тотално неясно, не е ясна долната и горна граница на числата, които да могат да бъдат въвеждани, ако въобще има такава граница. Какви точно библеотеки не могат да се ползват. Иначе в Линукс има библиотека да работиш със т. нар. software floating point, където числата могат да бъдат с произволна точност и големина ограничена само от паметта на компютъра ти.

[borovaka]

arda_kjv Мерси, първо ще опитам решението с разлагането на прости множители, после ще пробвам и логаритмите. Cmath мога да я използвам. Не могат да се използват библиотеки предназначени за работа с големи числа, иначе всичко стандартно в C++/STL е разрешено.
А колкото до големината на числата, те се ограничават до тип int.

[arda_kj]

Ако числата могат да бъдат отрицателни тогава ще трябва да ги третираш по някакъв друг начин, логаритъм от отрицателно реално число не е дефиниран. Също и нулата трябва да се третира отделно, ама тогава е лесно, щото каквото и да умножиш по нула е все нула.

[victim70]

Имам решение ако има реално ограничение на въвежданата матрица - пример:
елементите са в размера на int или long или long long, float, double. Дори да са по-големи има решение. В условието не видях никакво такова ограничение значи може едно от числата да е R^65536 примерно.
Навремето правих алгоритъм за смятане на Pi до 1024 знак на Правциум 8Д :-) на бейсик