Хостинг Портала RusFAQ.ru:
MosHoster.ru - Профессиональный хостинг на Windows 2008

РАССЫЛКИ ПОРТАЛА RUSFAQ.RU

Чемпионы рейтинга экспертов в этой рассылке

Лысков Игорь Витальевич Статус: Профессионал Рейтинг: 181 ∙ повысить рейтинг >>

Micren Статус: Студент Рейтинг: 114 ∙ повысить рейтинг >>

Person Статус: 3-й класс Рейтинг: 47 ∙ повысить рейтинг >>

/ КОМПЬЮТЕРЫ И ПО / Языки программирования / C/C++

Выпуск № 1245
от 19.02.2009, 17:05

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

Вопрос № 160.418

Здраствуйте уважаемые эксперты!Помогите пожалуйста написать и отладить программу исследующую один из вариантов алгоритма хеширования таблицы со строковыми ключами при нескольких значениях коэффициента заполнения.1)Преобразование строкового ключа в целое число:сложение двухбайтовых слов; при переполнении к сумме добавляется единица.2)Хеширование целочисленного ключа:алгоритм умножения.3)Разрешение коллизий:алгоритм квадратичных проб.

Отправлен: 14.02.2009, 02:30 Вопрос задал: Александр Сегеевич (статус: Посетитель) Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 1)

Отвечает: Ross Здравствуйте, Александр Сегеевич! http://rusfaq.ru/upload/1423 Мои наработки на тему хеш-таблиц. Реализован метод умножения для целочисленных ключей, хеширование строк проводится по алгоритму SDBM. Я думаю не очень сложно будет переделать для вашего случая. Что такое "метод квадратичных проб" я не знаю :( --------- Доступно только то, что видимо (c) Б. Керниган

Ответ отправил: Ross (статус: Практикант) Ответ отправлен: 16.02.2009, 16:41 Как сказать этому эксперту "спасибо"? Отправить SMS #thank 243788 на номер 1151 (Россия) | Еще номера >> Отправить WebMoney: Неплохо (10 руб.) Хорошо (15 руб.) Отлично (20 руб.) БЛЕСТЯЩЕ! (30 руб.) Вам помогли? Пожалуйста, поблагодарите эксперта за это! Оценка за ответ: 5 Комментарий оценки: Спасибо и за это!:))это уж лучше чем совсем ничего!:)

Вопрос № 160.422

Здравствуйте, дорогие эксперты! Мне очень нужно решить задачи по длинной арифметике! Пожалуйста, помогите решить! Первая задача: Сумма произведений Требуется вычислить сумму произведений цифр каждого N-значного числа. При этом следует учесть, что если в числе встречается цифра 0, то произведение его цифр равно нулю. Для N=3 искомая сумма представлена следующим рядом: S = 1*0*0 + 1*0*1 + 1*0*2 + … + 9*9*8 + 9*9*9 = 91125 Входные данные: В единственной строке входного файла INPUT.TXT записано натуральное число N (N < 1000). Выходные данные: В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — сумму произведений всех N-значных чисел. Примеры: 1. input.txt: 1 output.txt: 45 2. input.txt:3 output.txt:91125 3. input.txt:5 output.txt:184528125 Вторая задача: A-B Требуется найти разность между неотрицательными числами А и В. Входные данные: Во входном файле INPUT.TXT в двух строках записаны два неотрицательных целых числа A и B, не превышающие 101000. Выходные данные: В выходной файл OUTPUT.TXT выведите значение A-B. Примеры: 1. input.txt: 7 5 output.txt:2 2. input.txt: 5 17 output.txt:-12 Третья задача: Длинный корень По заданному натуральному числу А требуется найти наибольшее число В такое, что B2 <= A. Входные данные: Во входном файле INPUT.TXT записано натуральное число A (A <= 103000). Выходные данные: В выходной файл OUTPUT.TXT выведите максимальное натуральное число B, квадрат которого не превосходит A. Число B следует выводить без лидирующих нулей. Примеры: input.txt: 17 output.txt: 4 Заранее СПАСИБО!!!!

Отправлен: 14.02.2009, 06:31 Вопрос задал: Аршавин Александр Абрамович (статус: Посетитель) Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 0)

Отвечает: Micren Здравствуйте, Аршавин Александр Абрамович! Решение 1й задачи: Приложение: #include <fstream> #include <string> #include <vector> using namespace std; class longnum { private: typedef unsigned __int32 datatype; typedef unsigned __int64 extdatatype; typedef vector<datatype>::iterator itertype; typedef vector<datatype>::reverse_iterator ritertype; vector<datatype> _data; static const datatype div=1000000000; static const datatype num=9; public: longnum(datatype val=0) { _data.push_back(val); } longnum operator=(datatype val) { _data.clear(); _data.push_back(val); return *this; } longnum operator*(datatype val) { longnum res(*this); datatype carry=0; for(itertype it=res._data.begin();it!=res._data.end();it++) { extdatatype tmp=static_cast<extdatatype>(*it)*val+carry; *it=tmp%div; carry=static_cast<datatype>(tmp/div); } if(carry)res._data.push_back(carry); return res; } longnum operator*(longnum& val) { longnum res; res._data.resize(_data.size()+val._data.size(),0); for(itertype valit=val._data.begin();valit!=val._data.end();valit++) { vector<datatype> tmpdata(_data.size()+val._data.size(),0); itertype tmpit=tmpdata.begin()+(valit-val._data.begin()); datatype carry=0; extdatatype tmp; for(itertype it=_data.begin();it!=_data.end();it++,tmpit++) { tmp=static_cast<extdatatype>(*it)**valit+carry; *tmpit=tmp%div; carry=static_cast<datatype>(tmp/div); } *tmpit=carry; carry=0; for(itertype tmpit=tmpdata.begin(),resit=res._data.begin();tmpit!=tmpdata.end();tmpit++,resit++) { tmp=static_cast<extdatatype>(*tmpit)+*resit+carry; *resit=tmp%div; carry=static_cast<datatype>(tmp/div); } } return res; } friend ostream& operator<<(ostream& stream,longnum val); }; ostream& operator<<(ostream& stream,longnum val) { bool f=false; for(longnum::ritertype it=val._data.rbegin();it!=val._data.rend();it++) { if(!f) { if(*it) { f=true; stream<<*it; } } else { char buf[10]; _itoa(*it,buf,10); string str=buf; while(str.length()<longnum::num)str="0"+str; stream<<str; } } if(!f)stream<<"0"; return stream; }; longnum calc(unsigned int N) { if(N) { if(N==1)return 45; else { unsigned int t=N/2; return calc(t)*calc(N-t); } } else return 0; } int main() { unsigned int N; ifstream in("INPUT.TXT"); ofstream out("OUTPUT.TXT"); in>>N; out<<calc(N)<<endl; return 0; }

Ответ отправил: Micren (статус: Студент) Ответ отправлен: 14.02.2009, 10:30 Как сказать этому эксперту "спасибо"? Отправить SMS #thank 243613 на номер 1151 (Россия) | Еще номера >> Отправить WebMoney: Неплохо (10 руб.) Хорошо (15 руб.) Отлично (20 руб.) БЛЕСТЯЩЕ! (30 руб.) Вам помогли? Пожалуйста, поблагодарите эксперта за это!

Вопрос № 160.424

Добрый день! Вот у меня тут задали ещё задачи по комбинаторики. Помогите решить, пожалуйста! Первая задача: Великий комбинатор В результате очередной хитроумной комбинации у Остапа Бендера и его компаньонов - K детей лейтенанта Шмидта оказалось X рублей пятирублевыми банкнотами. И вот дело, как водится, дошло до дележа... Шура Балаганов предложил "по справедливости", т.е. всем поровну. Паниковский порешил себе отдать половину, а остальным "по заслугам". Каждый из K детей лейтенанта предложил что-нибудь интересное. Однако, у Великого Комбинатора имелось свое мнение на этот счет... Ваша же задача состоит в нахождении количества способов разделить имеющиеся деньги между всеми участниками этих славных событий: K детьми лейтенанта Шмидта и Остапом Бендером. Входные данные: Во входном файле INPUT.TXT записаны целые числа X (0 <= X <= 500) и K (0 <= K <= 100). Естественно, что число X делит ся на 5. Да и при дележе рвать пятирублевые банкноты не разрешается. Выходные данные: В выходной файл OUTPUT.TXT выведите одно целое число - количество способов дележа. Примеры: input.txt: 15 2 output.txt: 10 Второя задача: Шаблоны Шаблоном размера n назовем строку длины n, каждый из символов которой входит в множество {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, ?}. Шаблоны преобразуются в строки из цифр по следующим правилам: ∙ символы от 0 до 9 могут быть преобразованы только сами в себя; ∙ символ a может преобразован в любой из символов 0,1, 2, 3; ∙ символ b может преобразован в любой из символов 1,2,3,4; ∙ символ c может преобразован в любой из символов 2,3,4,5; ∙ символ d может преобразован в любой из символов 3,4,5,6; ∙ символ e может преобразован в любой из символов 4,5,6,7; ∙ символ f может преобразован в любой из символов 5,6,7,8; ∙ символ g может преобразован в любой из символов 6,7,8 ,9; ∙ символ ? может преобразован в любой из символов от 0 до 9; Даны два шаблона: p1 и p2. Рассмотрим множество S1 строк, которые могут быть получены из p1 по описанным правилам, и множество S2 строк, которые могут быть получены из p2. Необходимо найти количество строк, входящих в оба этих множества. Входные данные: Первая строка входного файла INPUT.TXT содержит шаблон p1, вторая — шаблон p2. Шаблоны имеют одинаковый положительный размер, не больше 9. Выходные данные: В выходной файл OUTPUT.TXT выведите ответ на задачу. Примеры: 1. input.txt: ??? abc output.txt: 64 2. input.txt: ??? 000 output.txt: 1 3. input.txt: abc 999 output.txt: 0 Третья задача: Две кучки камней У Вас есть N камней с массами W1, W2 , … WN. Требуется разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. Входные данные: В первой строке входного файла INPUT .TXT записано число N – количество камней (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы камней W1, W2 , … WN (1 ≤ Wi ≤ 105). Выходные данные: В единственную строку выходного файла OUTPUT.TXT нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух кучек. Примеры: 1. input.txt: 5 5 8 13 27 14 output.txt: 3 Спасибо большое!!!!

Отправлен: 14.02.2009, 06:47 Вопрос задал: Аршавин Александр Абрамович (статус: Посетитель) Всего ответов: 2 Мини-форум вопроса >>> (сообщений: 5)

Отвечает: Ross Здравствуйте, Аршавин Александр Абрамович! Решение последней задачи. Приложение: #include <algorithm> #include <vector> #include <fstream> using namespace std; class Application { public: Application(int argc, char** argv) { } void Run() { vector<int> stones = GetDataFromFile("INPUT.TXT"); int heap1, heap2; Dissolve(stones, heap1, heap2); ofstream oFile("OUTPUT.TXT", ios::trunc); oFile << abs(heap1 - heap2); oFile.close(); } private: vector<int> GetDataFromFile(const char* fileName) { vector<int> stones; ifstream iFile(fileName); if (iFile.fail()) { // return empty array if file reading fails. return stones; } int N, weight; iFile >> N; for (int i = 0; i<N; ++i) { iFile >> weight; stones.push_back(weight); } iFile.close(); return stones; } void Dissolve(const vector<int>& stones, int& heap1, int& heap2) { vector<int> stonesSortedDesc(stones); sort(reverse_iterator<vector<int>::iterator>(stonesSortedDesc.end()) ,reverse_iterator<vector<int>::iterator>(stonesSortedDesc.begin())); heap1 = heap2 = 0; for (vector<int>::const_iterator i = stonesSortedDesc.begin(); i != stonesSortedDesc.end(); ++i) { if (heap1 <= heap2) { heap1 += *i; } else heap2 += *i; } } }; void main(int argc, char** argv) { Application app(argc, argv); app.Run(); } --------- Доступно только то, что видимо (c) Б. Керниган

Ответ отправил: Ross (статус: Практикант) Ответ отправлен: 14.02.2009, 15:48 Как сказать этому эксперту "спасибо"? Отправить SMS #thank 243630 на номер 1151 (Россия) | Еще номера >> Отправить WebMoney: Неплохо (10 руб.) Хорошо (15 руб.) Отлично (20 руб.) БЛЕСТЯЩЕ! (30 руб.) Вам помогли? Пожалуйста, поблагодарите эксперта за это!

Отвечает: Micren Здравствуйте, Аршавин Александр Абрамович! Решение 2й задачи: Приложение: #include <fstream> #include <string> #include <map> using namespace std; typedef unsigned int uint; typedef string::iterator iterstr; const char tChars[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','?'}; const uint tCharsNum=sizeof(tChars)/sizeof(tChars[0]); const string tStr[tCharsNum]={"0","1","2","3","4","5","6","7","8","9","0123","1234","2345", "3456","4567","5678","6789","0123456789"}; map<char,string> tMap; void initialize() { for(uint i=0;i<tCharsNum;i++) { tMap[tChars[i]]=tStr[i]; } } uint charsIntersecting(char ch1,char ch2) { string tStr1=tMap[ch1],tStr2=tMap[ch2]; uint count=0; for(iterstr it=tStr1.begin();it!=tStr1.end();it++) { count+=tStr2.find(*it)!=string::npos; } return count; } int main() { initialize(); ifstream in("INPUT.TXT"); ofstream out("OUTPUT.TXT"); string str1,str2; getline(in,str1); getline(in,str2); unsigned int intersecting=0; if (str1.length()&&str2.length()) { intersecting=1; for(iterstr it1=str1.begin(),it2=str2.begin();it1!=str1.end()&&it2!=str2.end();it1++,it2++) { intersecting*=charsIntersecting(*it1,*it2); } } out<<intersecting<<endl; return 0; }

Ответ отправил: Micren (статус: Студент) Ответ отправлен: 15.02.2009, 03:17 Как сказать этому эксперту "спасибо"? Отправить SMS #thank 243654 на номер 1151 (Россия) | Еще номера >> Отправить WebMoney: Неплохо (10 руб.) Хорошо (15 руб.) Отлично (20 руб.) БЛЕСТЯЩЕ! (30 руб.) Вам помогли? Пожалуйста, поблагодарите эксперта за это!

© 2001-2009, Портал RusFAQ.ru, Россия, Москва. Авторское право: ООО "Мастер-Эксперт Про" Техподдержка портала, тел.: +7 (926) 535-23-31 Хостинг: "Московский хостер" Поддержка: "Московский дизайнер" Авторские права | Реклама на портале ∙ Версия системы: 5.13 от 01.12.2008
RusFAQ.ru | MosHoster.ru | MosDesigner.ru RusIRC.ru | Kalashnikoff.ru | RadioLeader.ru