Linux за българи: Форуми

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

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

Dynamic Allocation of Arrays ($2)

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

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

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

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

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

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

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

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

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

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

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

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

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

@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, където числата могат да бъдат с произволна точност и големина ограничена само от паметта на компютъра ти.

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

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

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

victim70 Ограничението е: Матрицата трябва да е с големина най-много 1000 реда и 100 колони.
Ограничението на числата които са въвеждат е да са от тип int без значение от знака значи не може да се използва unsigned.

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

при отрицателни числа мунис може да се изнесе пред логаритъма и минусите да се умножават (логаритмите събират). А за нулата просто се спира по-нататъшното смятане като безсмислено :)

victim70 Ограничението е: Матрицата трябва да е с големина най-много 1000 реда и 100 колони.
Ограничението на числата които са въвеждат е да са от тип int без значение от знака значи не може да се използва unsigned.

аз съм го правил на асемблер на Правец 82 само че за числата на Фибоначи, само че си е мъка от където и да го погледнеш. да не фоворим че работата с подобни числа се лимитира от паметта.
А 32к за число и 1000 реда е скромното 2^15000. Трудно може да се каже че оперирането с подобни числа е удобно :)

Тя ако беше лесна задачката нямаше да я дадат на състезание по програмиране :)
Май най-лесно ще стане със разлагането на числата на прости множители и събиране на степените на множителите им. Като цялата тази работа се записва в масив и след това да се сравняват масивите за всеки 2 колони.

Тя ако беше лесна задачката нямаше да я дадат на състезание по програмиране :)
Май най-лесно ще стане със разлагането на числата на прости множители и събиране на степените на множителите им. Като цялата тази работа се записва в масив и след това да се сравняват масивите за всеки 2 колони.

не е толкова просто, представи си ситуацията:
2**4*3**1 т.е. степени 4 и 1
2**1*3**2 т.е. степени 1 и 2

как ще сметнеш (просто) кое е по-голямо?

Нях, сериозно аз бих си написал няколко функции за превръщане на int стойности във/умножение/сравнение на големи числа, представени като низове. Въобще не е толкова някакъв rocket science цялата работа. Поне не и докато не се появи деление, което обаче в случая няма да се случи.

 

gat3way Я кажи как става номера с представянето като низове.

Обръщането на int в низ е елементарно - sprintf().

Умножението става точно както става на хартия в училище. Единствено ти трябва една табличка, която да ти match-ва число от 0...9 към ascii стойност.  Сравнението става също толкова елементарно - в ascii таблицата, цифрите 0..9 са наредени както трябва.

Обръщането на int в низ е елементарно - sprintf().

Умножението става точно както става на хартия в училище. Единствено ти трябва една табличка, която да ти match-ва число от 0...9 към ascii стойност.  Сравнението става също толкова елементарно - в ascii таблицата, цифрите 0..9 са наредени както трябва.

даже и ASCII не ти е нужно, просто записваш от 0 до 9 като число във всеки байт и си ги събираш, изваждаш, умножаваш като само следиш за >9
Така минаваш без таблицата

Може :)

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

Всичко това е ако няма делене. Деленето усложнява ужасно много цялата тази работа. В случаят обаче няма делене и не виждам нищо лошо да си направиш сам.....ъммм това което го правят разни библиотеки като GMP.

Цитат на: arda_kj в Oct 25, 2010, 16:04

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

при отрицателни числа мунис може да се изнесе пред логаритъма и минусите да се умножават (логаритмите събират). А за нулата просто се спира по-нататъшното смятане като безсмислено :)

Вярно че така може да се избегне проблема с минусите, добра идея :). Ами значи проблема с минусите е решен, остава borovaka да хвани и да го реализира, едва ли е повече от ден работа - писане и тестване. Само че той май тръгна по по-трудния начин.

@borovaka значи какво правиш ако решиш да реализираш с логаритми - първоа двете сравнявани колони търсиш отрицателни числа, ако са четен брой отриц. числа значи целия резултат от умножението ще е положителен ако са нечетен, резултата ще е отрицателен, Същото правиш за втората колона и ако двевте колони са с нечетен брой минуси и няма нулеви членове, тогава ги сравняваш, ако една от колоните е положителна и няма нули в нея то тя автоматично е по-голяма от отрицателната колона. Оттам като разбереш ква е колоната отрицателна или положителна, прилагаш логаритъм от абсолютната стойност на всяко число.
Сега като се замисля трябва също да измислиш как ще третираш случаите, когато N на брой от колоните са с равни стойности, тогава няма как да кажеш тая колона е по-голяма от оная колона.

Момци :), аз май взех, че я направих тая програма. Стана ми интересно да я реализирам с логаритмите и взех, че тая вечер я написах.

Кво прави програмата:
1) При стартиране програмата чете от Input.dat файла броя на редовете и колоните;
2) Изписва един report с инфо за потребителя и същия report се записва във лог файл matrix.log;
3) Попълва матрицата със случайни цели положителни числа;
4) Принтира на екрана матрицата;
5) После умножава числата във всяка колона чрез събиране на логаритми с отчитане на знака +/-;
6) Намира най-голямата колона;
7) Печата на екрана логаритмите от всички колони като показва най-голямата колона/колони с големи букви;
8) Принтира размера на матрицата;

Прикачвам файла със сорс кода и компилираната програма, който иска да ги разгледа и да си играе.