C++ Builder
| Главная | Уроки | Статьи | FAQ | Форум | Downloads | Литература | Ссылки | RXLib | Диски |

  ЗакрытаНовая темаНовый опрос
Помогите ПОжалуйста!!!!, СОС!!!!!!!!!!!!!&#
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. МГТУ им. Баумана говоришь? и учитель тупой? А как его по имени отчеству? smile.gif А ты уверен, что он сюда не заглядывает? А то были случаи, когда студенты думали, что они всех умнее, а оказывалось... smile.gif
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



Я конечно извиняюсь, но зачем писать то, что мне не надо.... Спасибо конечно за ценную информацию, уоторую вы мне написали, но лучше бы программу написали. Вот около меня учитель сидит и ждет пока я ее сдам! А я ее ни фига не понимаю!!!! Господи за что мне это наказание!!!!!!!sad.gif
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-х примеров было вполне достаточно!
Считаю что,если человек обладающий хоть какими-то знаниями в программировании(другой язык — например паскаль) возьмет и почитает
какую — нибудь книгу типа — "С/С++ для начинающих", разберется в этой задачке.
А если он ничего не хочет читать...,то хоть по символам ему диктуйте,толку не будет!
Без труда ,сами знаете... smile.gif
Для Daredevil
Почитайте что-нибудь по С/С++(любую книгу!)в любой Вы найдете ответы на все Ваши вопросы по данной задаче! wink.gif
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;
}
//--------------------------------------------------

Вернуться в Вопросы программирования в C++Builder
ЗакрытаНовая темаНовый опрос