VPF::Бинарный поиск - Форум программистов

Agarwaen

Дата 7.1.2007, 12:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Задание: вводится строка и ключевой символ. Нужно найти номера позиций этого символа в строке методом деления пополам. Вот код, но он ищет только одну позицию. Посоветуйте что можно сделать.

Код


#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <io.h>
#include <iomanip.h>
#define Nmax 255

typedef struct is{
         char symbol;
         int index;
         } isymbol;

int main()
{
char buffer[Nmax],key;
 printf("Enter the string(%d symbols) and press Enter:",Nmax);
 cin>>setw(Nmax)>>buffer;
 printf("Enter the key symbol to search and press Enter:");
 cin>>setw(1)>>key;

 int i,j,size;
 size=strlen(buffer);
 isymbol string[Nmax];
 for (i=0;i<size;i++)
      {
      string[i].symbol=buffer[i];
      string[i].index=i+1;
      }

 isymbol temp;
 for (i=0;i<size;i++)
     for (j=0;j<size;j++)
      if (string[i].symbol<string[j].symbol)
     {
     temp=string[j];
     string[j]=string[i];
     string[i]=temp;
     }

 int m,t=0,b=size;
 while (t<=b)
   {m=(t+b)/2;
   if (string[m].symbol<key) t=m+1;
     else b=m-1;
   if (string[m].symbol==key)
    printf("\n Position of key symbol: %d",m);
   }
return 0;
}

Это сообщение отредактировал(а) Agarwaen - 7.1.2007, 12:30

Kuvaldis

Дата 7.1.2007, 13:08 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 11
Всего: 61

Agarwaen,

Цитата

Нужно найти номера позиций этого символа в строке методом деления пополам.

Метод деления пополам применяется только к отсортированным данным
Есть обобщение данного метода, которое ищет именно ПЕРВОЕ вхождение символа в строку (остальные получить несложно, нужно лишь запустить цикл: пока символ справа равен искомому, увеличивать счетчик и продвигаться по сортированной строке вправо)

Код


int L, R;

L = 0;
R = N;  // длина строки
while (L > R)
{
        m = (L + R) / 2;
        if (str[m] < x)
              L = m + 1;
        else
              R = m;
}

if (str[m] == x)
 // нашли
else
 // не нашли

Т.е. увеличиваем индекс только при поиске в правой половине

Это сообщение отредактировал(а) Kuvaldis - 7.1.2007, 13:09

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Agarwaen

Дата 7.1.2007, 18:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Не пойму как это работает. Можно поподробней?

Agarwaen

Дата 7.1.2007, 20:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Вот функция, возвращает 1 значение. Как её можно изменить?

Код


int find(struct is s[], int n, char key)
{
    int a,b,m;
     for (a=0,b=n-1;a<=b;)
     {
     m=(a+b)/2;
     if (s[m].symbol==key) return s[m].index;
     if (s[m].symbol>key)
      b = m-1;
     else
      a = m+1;
     }
return -1;
}

Kuvaldis

Дата 7.1.2007, 20:43 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 11
Всего: 61

Agarwaen,

Код


//-------------------------------------------------------------
#include <stdio.h>    
#include <conio.h>
#include <string.h>    
#include <iostream.h>
#include <iomanip.h>
//-------------------------------------------------------------    
#define Nmax 255    
//-------------------------------------------------------------
typedef struct is
{    
    char symbol;    
    int index;    
} isymbol;    
//-------------------------------------------------------------
int main()    
{    
    char  buffer[Nmax];
    char  key;
    
    printf("Enter the string (%d symbols) and press Enter: \n",Nmax);    
    cin >> setw(Nmax) >> buffer;    
 
    printf("Enter the key symbol to search and press Enter:");    
    cin >> setw(1) >> key;    
 
    int i,j,size;    
 
    size = strlen(buffer);    
    isymbol string[Nmax];    
 
    for (i = 0; i < size; i++)    
    {    
        string[i].symbol = buffer[i];    
        string[i].index = i;    
    }    
 
    isymbol temp;    
    // сортировка символов  (обычный пузырек)
    for (i = 0; i < size - 1; i++)
    {
        for (j = 1; j < size - i; j++)
        {
            if (string[j - 1].symbol > string[j].symbol)    
            {    
                temp = string[j];    
                string[j] = string[j - 1];
                string[j - 1] = temp;    
            }    
        }
    }

    int m, l = 0, r = size - 1;    
 
    while (l < r)    
    {
        m = (l + r) / 2;    
        if (string[m].symbol < key) 
            l = m + 1;    
        else 
            r = m;    
    }

    if (string[r].symbol == key)    // совпадение было
    {

        printf("\n Positions of key symbol %c are: \n", key);
        do
        {
            cout << string[r].index << ' ';
            r++;    // перейти к следующему символу в отсортированном массиве
        }
        while (string[r].symbol == key);
    }
    else
        cout << "No match" << endl;

    getch();
    return 0;
}
//-------------------------------------------------------------

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Agarwaen

Дата 7.1.2007, 21:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Огромное спасибо. И ещё такой вопрос: какой метод сортировки самый быстрый?

KpoHyc

Дата 7.1.2007, 21:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 23.12.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 5

Agarwaen, так и называйется "Быстрая сортировка" Чарльз Хоар автор...

--------------------

AScript + Pascal + C -> C++ ->C#Adobe Photoshop 7.0/CS 2.0 + GIMP+ Visual Studio .NET(sp1)/2005 pro(sp1)

Agarwaen

Дата 7.1.2007, 21:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Странно, когда вводишь в строке пробел, то он сбрасывает в ключ первый символ и всё. В чём дело?

Agarwaen

Дата 8.1.2007, 00:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Блин не пойму почему строка записывается в buffer до первого пробела.

Код


    char* buffer=new char[Nmax];
    char  key;

    clrscr();
    printf("Enter the string (%d symbols) and press Enter: ",Nmax);
    scanf("%s",buffer);
    /*cout.unsetf(ios::skipws);
    cin >> setw(Nmax) >> buffer;*/

    printf("\n Enter the key symbol to search and press Enter:");
    cout << (key=getch());

Agarwaen

Дата 8.1.2007, 04:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Вот посмотрите этот код. Какие общие замечания? По-прежнему есть проблемы с пробелами во входной строке, может кто подскажет. И ещё насколько здесь оправдано использование ввода/вывода через потоки? Заранее спасибо.

Код


//-------------------------------------------------------------
#include <stdio.h>
#include <conio.h>
#include <string.h>
//-------------------------------------------------------------
#define Nmax 128
//-------------------------------------------------------------
typedef struct IS
{
    char symbol;
    int index;
} isymbol;
void sort(struct IS[], int);
void bisearch(struct IS[], char, int);
//-------------------------------------------------------------
void main()
{
  char buffer[Nmax];
  char key;

  clrscr();
  printf("===========================Binary search========================\n");
  printf("   Enter the string and press Enter: ");
  scanf("%s",buffer);

  int i,size;
  size = strlen(buffer);
  isymbol string[Nmax];

  for (i = 0; i < size; i++)
    {
    string[i].symbol = buffer[i];
    string[i].index = i+1;
    }

  sort (string, size);

  do
    {
    printf("\n   Enter the key symbol to search and press Enter:");
    key = getch();
    printf(" %c\n",key);
    printf("\n=============================Search=============================\n");
    bisearch(string, key, size);
    printf("\n   Press y to continue, any other key to exit:");
    }
  while (getch()=='y');
}
//-------------------------------------------------------------
void sort(struct IS s[], int size)
{
  int i,j;
  isymbol temp;
  for (i = 0; i < size - 1; i++)
    {
    for (j = 1; j < size - i; j++)
      {
      if (s[j - 1].symbol > s[j].symbol)
    {
    temp = s[j];
    s[j] = s[j - 1];
    s[j - 1] = temp;
    }
      }
    }
}
//-------------------------------------------------------------
void bisearch(struct IS s[], char key, int size)
{
  int m = 0, l = 0, r = size - 1;
  while (l < r)
    {
    m = (l + r) / 2;
    if (s[m].symbol < key)
    l = m + 1;
    else
    r = m;
    }
   if (s[r].symbol == key)
    {
    printf("\n   Position(s) of key symbol %c are: ", key);
    do
      {
      printf(" %d", s[r].index);
      r++;
      }
    while (s[r].symbol == key);
    }
   else
      printf("\n   Position(s) of key symbol %c are: No solution", key);
}

Kuvaldis

Дата 8.1.2007, 10:42 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 11
Всего: 61

Agarwaen,

Цитата

По-прежнему есть проблемы с пробелами во входной строке, может кто подскажет.

Такой принцип работы у cin и scanf при работе со строками. Чтобы изменить ситуацию, можно:
1. С:
fgets(char* str, int maexlen); используем эту функцию, подробности по F1

2. C++:
cin.getline(char* str, int maxlen);
подробности также по F1

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Agarwaen

Дата 8.1.2007, 13:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 4.1.2007

Репутация: нет
Всего: нет

Спасибо, ты мне очень помог. Использую наверно gets(buffer).

sergejzr

Дата 8.1.2007, 14:08 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360

Существует стандартная функция сортировки "qsort".
Ей сортировать лучше и быстрее всего.

Код


#include <iostream>
#include "stdlib.h"
using namespace std;
#define Nmax 26
int compareChar(const void *first,const void *second)
{
char *firstc=(char*)first;
 char *secondc=(char*)second;
return (*firstc)-(*secondc);
//return (*secondc)-(*firstc); //Если сортируем в обратном порядке
}
int main()
{
char buffer[Nmax];
int i;
for(i=0;i<Nmax;i++)
{
buffer[i]=25-i+'A';
}
cout<<"Do sortirovki"<<endl;
for(i=0;i<Nmax;i++)
{
cout<<buffer[i];
}
cout<<endl;
qsort ( buffer, Nmax, sizeof(char), compareChar);

cout<<"Posle sortirovki"<<endl;
for(i=0;i<Nmax;i++)
{
cout<<buffer[i];
}
cin>>i;
}

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »