| Daredevil |
| Отправлено: 26.09.2003, 14:06 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
Мне срочно надо написать программу:
Задано слово четной длины. Выявить, в какой половине буква «А» встречается чаще?
А наш учитель тупой, он ни одной команды не хочет объяснять, а я С++ вижу в 3 раз в жизни...... Люди, помогите пожалуйста! НЕ бросайте бедного студента МГТУ! |
|
| Георгий |
| Отправлено: 26.09.2003, 19:22 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
Тяжёлый случай — на С такие задачи задавать — на asm`е такое написать — я бы ещё понял, но на си...
| CODE | #include <iostream.h>
void main(void)
{
const char Etalon='а';
const char Word[]="магазина";//в маскве па паследним сведениям 1.2 млн азербайджан паэтаму подразаем им в написании слов
int i,Count[2]={0,0};
const int WordLen=sizeof(Word)/sizeof(Word[0]);
for (i=0; i < WordLen; i++)
{
if ( Word[i] == Etalon )
Count[i/(WordLen>>1)]++;
};
cout<<" в слове \""<<Word<<"\" символ '"<<Etalon<<"' ";
if ( Count[0]==Count[1] )
{
cout<<"одинаково часто встречается и в левой и в правой частях"<<endl;
}
else {
cout<< чаще всего встречается в "<<((Count[0]>Count[1])?"левой":"правой")<<" части слова"<<endl;
};
}; |
PS. отладку оставляю тебе — я даже не утверждаю, что код вообще работоспособен...
PPS. МГТУ им. Баумана говоришь? и учитель тупой? А как его по имени отчеству?  А ты уверен, что он сюда не заглядывает? А то были случаи, когда студенты думали, что они всех умнее, а оказывалось... |
|
| Admin |
| Отправлено: 26.09.2003, 21:03 |
|
Владимир
Группа: Администратор
Сообщений: 1190
|
Интересно на каком курсе ? Если на первом, то ладно.
Для более высоких — слишком легкая задача.
(Слишком солидный и приличный институт)
Для C++Builder без усложнений:
| CODE |
void __fastcall TForm1::Button1Click(TObject *Sender)
{
AnsiString s,s1,s2;
s = Edit1->Text; // слово четной длины
int n = s.Length();
s1 = s.SubString(1,n/2);
s2 = s.SubString(n/2+1,n/2);
int c1=0,c2=0;
for(int i=1; i<=n/2; i++){
if(s1[i] == 'A') c1++;
if(s2[i] == 'A') c2++;
}
if(c1 > c2) ShowMessage("В левой части больше");
if(c1 < c2) ShowMessage("В правой чати больше");
if(c1 == c2) ShowMessage("Одинаковы");
} |
|
|
| Георгий |
| Отправлено: 27.09.2003, 01:28 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
Владимир
Да так я же для него наоборот накрутил по максимуму — чтобы он хоть под конец 4-й учебной недели (не знаю, как в МГТУ, а в МИФИ счёт времени идёт по неделям) взял какую-нибудь книжку про С и прочитал — пользы будет больше. |
|
| Георгий |
| Отправлено: 27.09.2003, 18:29 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
Давно я такого кайфа не получал:
Ради интереса решил посмотреть, у когоже код быстрее работает — у меня или у Владимира... Получилось, что у него (ну это после того, как я от AnsiString`а избавился и оставил только идею деления строки на 2 части)...
непорядок! надо исправить!
<спустя 5 часов>
Даже последний вариант моего алгоритма (без разбива строки на 2 части), несмотря на, то, что он стал работать быстрее сишного варианта алгоритма Владимира, всё равно проигрывал asm варианту Владимира на моём домашнем Athlon`е.
...
сокращения:
мв — мой вариант алгоритма
вв — Владимира вариант алгоритма
краткое описание функций:
method1 — мв со стандартными оптимизациями
method2 — вв без оптимизаций
method3 — вв без использования объектов AnsiString и со стандартными оптимизациями
method4 — аналог method1, но без использования операции деления
method5 — мв, но для поиска используется библиотечная функция
method6 — мв, но тупо набранный на asm`е — как факт он медленнее чем method3
method7 — вв, набран на asm со стандартными оптимизациями
method8 — пустая функция — время её работы = накладным расходам
method9 — мв, лучшее, что я смог сделать с последовательным поиском
method10 — вв, попробовал ещё чуть чуть улучшить — теперь на длинных словах быстрее, чем method7
method11 — вв, реализованный на rep scasb
то, что у меня выводится при запуске:
результаты работы:
испытания 1-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 241 тактов процессора
испытания 2-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 3842 тактов процессора
испытания 3-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 142 тактов процессора
испытания 4-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 169 тактов процессора
испытания 5-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 205 тактов процессора
испытания 6-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 160 тактов процессора
испытания 7-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 116 тактов процессора
испытания 8-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 15
этот метод в среднем был выполнен за 33 тактов процессора
испытания 9-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 145 тактов процессора
испытания 10-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 101 тактов процессора
испытания 11-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 176 тактов процессора
а без не нужный сведений (все времена в тактах):
1 = 241
2 = 3842
3 = 142
4 = 169
5 = 205
6 = 160
7 = 116
8 = 33
9 = 145
10 = 101
11 = 176
Моя домашняя машина — Athlon XP торобред 200x9.5
Владельцы других систем — скажите, что у вас со временами выполнения различных методов рассчёта поставленной задачи.
Особенно меня интересует P4 — у него якобы должны быть совсем другие времена (по крайней мере в тактах).
ссылки на проект и exe прилагаются.
rdtsc_exe
rdtsc_src
всё, устал, да и лучше, чем есть не получается...
Если кто сможет быстрее сделать, то буду рад.
Блин какая-то хрень творится с hotbox — *.rar битые закачиваются, а *.zip нормально... Поэтому пишу код:
| CODE | __int64 GetCPUClock(void)
{
unsigned long a,b;
asm {
rdtsc;
mov a,eax;
mov b,edx;
};
__int64 ret;
((unsigned long*)&ret)[0]=a;
((unsigned long*)&ret)[1]=b;
return ret;
};
void method1(unsigned int Elems[2], const char* Word, int WordLen, const char Etalon)
{
int i,n=WordLen>>1;
Elems[0]=Elems[1]=0;
for (i=0; i < WordLen; i++)
{
if ( Word[i] == Etalon )
Elems[i/n]++;
};
};
void method2(unsigned int Elems[2], const char* Word, int WordLen, const char Etalon)
{
AnsiString s,s1,s2;
s = Word;
int n = WordLen;
s1 = s.SubString(1,n/2);
s2 = s.SubString(n/2+1,n/2);
Elems[0]=Elems[1]=0;
for(int i=1; i<=n/2; i++){
if(s1[i] == Etalon ) Elems[0]++;
if(s2[i] == Etalon ) Elems[1]++;
}
};
void method3(unsigned int Elems[2], const char* s1, int WordLen, const char Etalon)
{
WordLen>>=1;
const char *s2=&s1[WordLen];
Elems[0]=Elems[1]=0;
for(int i=0; i<WordLen; i++){
if(s1[i] == Etalon ) Elems[0]++;
if(s2[i] == Etalon ) Elems[1]++;
}
};
void method4(unsigned int Elems[2], const char* Word, int WordLen, const char Etalon)
{
int i;
int n=WordLen>>1;
Elems[0]=Elems[1]=0;
for (i=0; i < WordLen; i++)
if ( Word[i] == Etalon )
Elems[i>n]++;
};
void method5(unsigned int Elems[2], const char* Word, int n, const char Etalon)
{
n>>=1;
Elems[0]=Elems[1]=0;
char * ptrStr=(char*)Word;
ptrStr=strchr(ptrStr,Etalon);
while( ptrStr )
{
Elems[(ptrStr-Word)>n]++;
ptrStr=strchr(ptrStr+1,Etalon);
};
};
void method6(unsigned int Elems[2], const char* ptrWord, int WordLen, const char Etalon)
{
asm {
xor eax,eax;
mov esi, Elems;
mov ecx,WordLen;
mov bl,Etalon;
mov dword ptr [esi+0],eax;
mov dword ptr [esi+4],eax;
mov edx,esi;
shr ecx,1;
mov esi,ptrWord;
mov edi,esi;
add esi,ecx;
method6L1:
mov ah,byte ptr [esi];//загрузка байта из второй половины слова
mov al,byte ptr [edi];//загрузка байта из первой половины слова
cmp bl,ah;
jne method6L2;
inc dword ptr [edx+4];
method6L2:
cmp bl,al;
jne method6L3;
inc dword ptr [edx+0];
method6L3:
inc esi;
inc edi;
loop method6L1;
};
};
void method7(unsigned int Elems[2], const char* ptrWord, int WordLen, const char Etalon)
{
asm {
xor eax,eax;
mov esi, Elems;
mov ecx,WordLen;
mov dword ptr [esi+0],eax;
mov dword ptr [esi+4],eax;
mov al,Etalon;
mov edx,esi;
shr ecx,1;
mov esi,ptrWord;
mov edi,esi;
add esi,ecx;
method7L1:
cmp al,byte ptr [esi];
jne method7L2;
inc dword ptr [edx+4];
method7L2:
cmp al,byte ptr[edi];
jne method7L3;
inc dword ptr [edx+0];
method7L3:
inc esi;
inc edi;
dec ecx;
jnz method7L1;
};
};
void method8(unsigned int[2], const char* , int , const char )
{
};
void method9(unsigned int Elems[2], const char* ptrWord, int WordLen, const char Etalon)
{
asm {
mov edx,Elems;
mov ecx,WordLen;
mov esi,ptrWord;
xor ebx,ebx;
shr ecx,1;
mov al,Etalon;
mov edi, ecx;
method9L1:
cmp al,byte ptr [esi];
jne method9L2;
inc ebx;
method9L2:
inc esi;
dec ecx;
jnz method9L1;
mov ecx, edi;
mov dword ptr [edx+0], ebx;
xor ebx,ebx;
method9L3:
cmp al,byte ptr [esi];
jne method9L4;
inc ebx;
;inc edi;
method9L4:
inc esi;
dec ecx;
jnz method9L3;
mov dword ptr [edx+4], ebx;
;mov dword ptr [edx+4], edi;
};
};
void method10(unsigned int Elems[2], const char* ptrWord, int WordLen, const char Etalon)
{
asm {
mov ecx,WordLen;
xor eax,eax;
mov edi,ptrWord;
mov esi, Elems;
mov dword ptr [esi+0],eax;
mov dword ptr [esi+4],eax;
shr ecx,1;
mov bl,Etalon;
mov edx,esi;
mov esi,ptrWord;
add edi, ecx;
method10L1:
dec ecx;
cmp bl,byte ptr [esi];
sete al;
add dword ptr [edx+0], eax;
cmp bl,byte ptr[edi];
sete al;
add dword ptr [edx+4], eax;
inc esi;
inc edi;
test ecx,ecx;
jnz method10L1;
};
};
void method11(unsigned int Elems[2], const char* ptrWord, int WordLen, const char Etalon)
{
asm {
mov edx,Elems;
mov ecx,WordLen;
mov edi,ptrWord;
xor ebx,ebx;
shr ecx,1;
mov al,Etalon;
push ecx;
method11L2:
repne scasb;
jne method11L1;
inc ebx;
jmp method11L2;
method11L1:
mov dword ptr [edx+0], ebx
pop ecx;
xor ebx,ebx;
method11L3:
repne scasb;
jne method11L4;
inc ebx;
jmp method11L3;
method11L4:
mov dword ptr [edx+4], ebx;
};
};
struct MethodTime
{
void(*Method)(unsigned int[2],const char*,int,const char);
__int64 Time;
unsigned int Values[2];
};
void __fastcall TForm1::Button1Click(TObject *Sender)
{
__int64 Before,After;
MethodTime methods[11];
const char* Word = new char[ Edit1->Text.Length() + 1 ];
strcpy( (char*)Word, Edit1->Text.c_str() );
const char Etal=this->Edit2->Text[1];
int i,j;
const int WordLen=strlen(Word);
const int RepCount=1000000;
methods[0].Method=method1;
methods[1].Method=method2;
methods[2].Method=method3;
methods[3].Method=method4;
methods[4].Method=method5;
methods[5].Method=method6;
methods[6].Method=method7;
methods[7].Method=method8;
methods[8].Method=method9;
methods[9].Method=method10;
methods[10].Method=method11;
//цикл рассчёта временных характеристик
for (i=0; i<(sizeof(methods)/(sizeof(methods[0]))); i++)
{
methods[i].Time=0;
for (j=0;j<RepCount;j++)
{
Before=GetCPUClock();
methods[i].Method(methods[i].Values,Word, WordLen,Etal);
After=GetCPUClock();
methods[i].Time+=After-Before;
}
};
//формирование отчёта
this->Memo1->Lines->Add("результаты работы:");
AnsiString str;
for (i=0;i<(sizeof(methods)/(sizeof(methods[0])));i++)
{
str="испытания ";str+=AnsiString(i+1);str+="-го метода показали:";
this->Memo1->Lines->Add(str);
str="символов \"";str+=AnsiString(Etal);str+="\" найдено в левой части слова \"";
str+=Word;str+="\" ";
str+=methods[i].Values[0];str+=" а в правой ";str+=methods[i].Values[1];
this->Memo1->Lines->Add(str);
str="этот метод в среднем был выполнен за ";str+=AnsiString(methods[i].Time/RepCount);
str+=" тактов процессора";
this->Memo1->Lines->Add(str);
};
delete Word;
} |
Отредактировано Георгий — 28/09/2003, 02:34 |
|
| Георгий |
| Отправлено: 29.09.2003, 23:36 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
посмотрел, я как это на tualin`е (P3 celeron) работает — по тактам похоже на athlon, но:
1. выше накладные расходы на тестированое (тест с пустой функцией = method8 выполняется у меня за 33 такта, а на celeron`е за 72 такта), но это не страшно — возможно доступ к MSR у интела больше времени занимает.
2. для интела (на примере селерона) самый быстрый метод рассчёта — 7-й, а для athlon`а 10-й...
3. сишные функции примерно одинаково по времени выполняются, поэтому писатели на ЯВУ могут не нервничать и быть уверенным, что для них никакой разницы между athlonXP и p3 нет, а вот, что же творится на p4 я ещё не видел — а там должно быть самое интересное.
PS. ну, что — кто со мной на перегонки?
celeron tualin 1400MHz:
результаты работы:
испытания 1-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 271 тактов процессора
испытания 2-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 4762 тактов процессора
испытания 3-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 184 тактов процессора
испытания 4-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 219 тактов процессора
испытания 5-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 239 тактов процессора
испытания 6-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 201 тактов процессора
испытания 7-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 165 тактов процессора
испытания 8-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 72 тактов процессора
испытания 9-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 189 тактов процессора
испытания 10-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 171 тактов процессора
испытания 11-го метода показали:
символов "н" найдено в левой части слова "перпендикулярность" 1 а в правой 1
этот метод в среднем был выполнен за 261 тактов процессора |
|
| Daredevil |
| Отправлено: 03.10.2003, 13:39 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
Я конечно извиняюсь, но зачем писать то, что мне не надо.... Спасибо конечно за ценную информацию, уоторую вы мне написали, но лучше бы программу написали. Вот около меня учитель сидит и ждет пока я ее сдам! А я ее ни фига не понимаю!!!! Господи за что мне это наказание!!!!!!! |
|
| Admin |
| Отправлено: 03.10.2003, 14:18 |
|
Владимир
Группа: Администратор
Сообщений: 1190
|
| QUOTE | | Спасибо конечно за ценную информацию, уоторую вы мне написали, но лучше бы программу написали |
Так написали = целых 2 шт.
Через какой компилятор будете компилить ?
Если нужно через C++Builder — вариант Admin.
Если чистый C++ — вариант Георгий.
----
Осталось только подсунуть код компилятору, откомпилить,
исправить встретившиеся ошибки и все.
Вроде как с 26/09 (когда ответили) по сегодня (03/10),
куча дней прошло (8), можно было-бы при желании найти
5 минут и любой код проверить (за 5 мин.)
----
Или, как говорил мой нехороший знакомый:
Нэ пытайся мэня объебать ! Я корэнной моськьвичь !
Я в Москва ужэ 10 лэт живююю !
Вот полностью рабочий код на любом компиляторе С++:
(вариант Георгия)
| CODE |
//---------------------------------------------------------------------------
#include <iostream.h>
#include <conio.h>
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
const char Etalon='a'; // символ который чаще встречается
const char Word[]="carantinaasa"; // слово в котром ищут
int i,Count[2]={0,0};
const int WordLen=sizeof(Word)/sizeof(Word[0]);
for (i=0; i < WordLen; i++)
{
if ( Word[i] == Etalon )
Count[i/(WordLen>>1)]++;
};
cout<<" in word \""<<Word<<"\" letter '"<<Etalon<<"' ";
if ( Count[0]==Count[1] )
{
cout<<"left == right"<<endl;
}
else {
cout<< "biger in "<<((Count[0]>Count[1])?"left":"right")<<" part of word"<<endl;
}
char ch = getch(); ch = ch;
return 0;
}
//------------------------------------------------------------
|
Подсуньте его компилятору и смотрите результаты !
Отредактировано Admin — 03/10/2003, 15:30
|
|
| Admin |
| Отправлено: 03.10.2003, 15:40 |
|
Владимир
Группа: Администратор
Сообщений: 1190
|
Если нужно вообще обойтись, даже без C++
а на чистом C, то вот такой вариант:
(переделанный вариант Георгия на С)
| CODE |
#include <stdio.h>
#include <conio.h>
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
char ch;
const char Etalon='a';
const char Word[]="carantinaasa";
int i,Count[2]={0,0};
const int WordLen=sizeof(Word)/sizeof(Word[0]);
for (i=0; i < WordLen; i++)
if ( Word[i] == Etalon ) Count[i/(WordLen>>1)]++;
printf("in word '%s' letter '%c' ",Word,Etalon);
if ( Count[0]==Count[1] ) printf("left == right\n");
else {
printf("biger in ");
if(Count[0]>Count[1]) printf("left"); else printf("right");
printf(" part of word");
}
ch = getch(); ch = ch;
return 0;
}
//-------------------------------------- |
|
|
| Иван |
| Отправлено: 03.10.2003, 17:45 |
|
Машинист паровоза
Группа: Участник
Сообщений: 207
|
Мдааа...!?
Вот во что может обернуться на первый взгляд простенькая задачка!
Я уважаю мнения Георгия и Владимира,но по-моему так Вы больше запутаете человека!Мне кажется что первых 2-х примеров было вполне достаточно!
Считаю что,если человек обладающий хоть какими-то знаниями в программировании(другой язык — например паскаль) возьмет и почитает
какую — нибудь книгу типа — "С/С++ для начинающих", разберется в этой задачке.
А если он ничего не хочет читать...,то хоть по символам ему диктуйте,толку не будет!
Без труда ,сами знаете...
Для Daredevil
Почитайте что-нибудь по С/С++(любую книгу!)в любой Вы найдете ответы на все Ваши вопросы по данной задаче! 
|
|
| Admin |
| Отправлено: 06.10.2003, 19:05 |
|
Владимир
Группа: Администратор
Сообщений: 1190
|
| CODE |
//---------------------------------------------------------------------------
#pragma hdrstop
#include <stdio.h>
#include <conio.h>
//---------------------------------------------------------------------------
#pragma argsused
int main(int argc, char* argv[])
{
char ch;
char Etalon;
int WordLen;
char Word[100];
int i,Count[2]={0,0};
printf("Input word: ");
for(i=0; i<100; i++) Word[i] = 0;
scanf("%s",Word); ch=getchar();// input word
for(i=0; i<100; i++) if(Word[i] == 0) { WordLen=i; break; }
printf("\nCount letter in word — %d\n",WordLen);
if(WordLen%2!=0) { printf("Not event word !"); ch=getch(); return; }
printf("Input letter: "); Etalon = getchar();
for (i=0; i < WordLen; i++)
if ( Word[i] == Etalon ) {
if(i < WordLen/2) Count[0]++; else Count[1]++;
}
printf("\n in word '%s' letter '%c' ",Word,Etalon);
if ( Count[0]==Count[1] ) printf("left == right\n");
else {
printf("biger in ");
if(Count[0]>Count[1]) printf("left"); else printf("right");
printf(" part of word");
}
printf("\nin left = %d, in right = %d",Count[0],Count[1]);
ch = getch(); ch = ch;
return 0;
}
//-------------------------------------------------- |
|
|
|
