VPF::[c++] бинарный поиск - Форум программистов

vorovaika

Дата 29.4.2008, 01:20 (ссылка)

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

Загрузка ...

Новичок

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

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

подскажите, пожалуйста, как исправить...Данная программа выполняет поиск в двумерном массиве по четным столбцам последовательный и бинарный...последовательный работает замечательно.. а с бинарным проблемы..то не ищет, то(если два одинаковых элемента в столбце ) выводит один из них.
Я пыталась прировнять его к 1000, но ничего не выходит, так как в этом случае он выполняет поиск
ar[mid][j]<el

ar[row][col] исходный массив, mid-средний элемент, el - элемент, который ищем
Помогите,пожалуйста...

Код


//поиск элемента (последовательности) по четным столбцам.
#include "stdafx.h"
#include <windows.h> 
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <time.h>
using namespace std;

HANDLE hStdout;
int main ()
{
int i,j,el,m,k,kol=0, w,last,first,mid,row,col, **ar;
srand(time(0));
hStdout = GetStdHandle(STD_OUTPUT_HANDLE); 
SetConsoleTextAttribute(hStdout, BACKGROUND_INTENSITY); 
SetConsoleTextAttribute(hStdout, FOREGROUND_GREEN); 

    SetConsoleTextAttribute(hStdout, 11);
    printf("Vveddite kolichestvo strok > 0\n");
            cin>>row;
printf("Vvedite kolichestvo stolbtsov> 0\n");
                cin>>col;
        
    SetConsoleTextAttribute(hStdout, 11);
printf("\n");
printf("Isxodnaya matritsa:\n");
    printf("\n");
ar=new int* [row];
for (i=0; i<row; i++)
ar[i]=new int[col];
  for(i = 0;i < row;++i)
   {
       ar[i] = new int[col];
       for(j = 0;j < col;++j)
           ar[i][j] = rand() % 99;
   }
          for (i=0; i<row; i++)
      {
          for (j=0; j<col; j++)
        {
            printf ("%2d",ar[i][j]);
            printf("  ");
        }
        printf("\n");
      }
    printf("\n");

// Сортировка отбором

    for (j=0; j<col; j++)
        for (m=0; m<row-1; m++)
          for (i=m+1; i<row; i++)
          {              
              if (ar[i][j]<ar[m][j])
                {
                  w=ar[m][j]; 
                  ar[m][j]=ar[i][j];
                  ar[i][j]=w;
                 }
                  }
          SetConsoleTextAttribute(hStdout, 13);
          printf("Otsortirovan metodom otbora po vozrastaniyu:\n");
        
    for (i=0; i<row; i++)
      {
          for (j=0; j<col; j++)
        {
            printf ("%2d",ar[i][j]);
            printf("  ");
            
        }printf("\n");
            
      }



SetConsoleTextAttribute(hStdout, 11);
printf("Kakoi elemens ishem? \n");
    printf("\n");
cin>>el;
    printf("\n");

    // Последовательнный поиск
SetConsoleTextAttribute(hStdout, 11);
printf("POSLEDOVATELNII POISK \n");
    printf("\n");
    for (j=0; j<col; j+=2)
    {
    for (i=0; i<row; i++)
        {
        if (ar[i][j]==el)
            {kol++;
                SetConsoleTextAttribute(hStdout, 12);
            printf("nomer %d  v %i stolbtse \n", i, j);                    
            printf("\n");
        }        }    } 
    if(kol==0)
        {
            printf("ne naiden\n");
        }
        
printf("\n");
//Бинарный поиск
SetConsoleTextAttribute(hStdout, 11);
printf("BINARNII POISK \n");
    printf("\n");
    
for(k=0; k<1000; k++)
{
for (j=0; j<row; j+=2)
          {    
        first=0;
        last=row-1;
        mid=(first+last)/2;
        do
        {
             if (ar[mid][j]<el)
               {
                  first=mid; 
               }
             else
               {
                 last=mid;    
               }
             mid=(first+last)/2;            
          } 

        while ((ar[mid][j]!=el) & (first<last)& (first>=0)& (last<row) & (mid>first) & (mid<last));


            while(ar[mid][j]==el)
          {
              kol++;
        SetConsoleTextAttribute(hStdout, 12);
            printf("nomer %2d v %2d stolbtse\n", mid, j);
            
            ar[mid][j]=1000;
          }

            
}}
     if(kol==0)
             {
            printf(" ne naiden \n");
             
           }
SetConsoleTextAttribute(hStdout, 11);
printf("\n");
    
cout<<"Press any key to exit...";
_getch();
return 0;
}

vorovaika

Дата 13.5.2008, 22:23 (ссылка)

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

Загрузка ...

Новичок

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

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

никто не знает?=(

t_gran

Дата 14.5.2008, 05:12 (ссылка)

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

Загрузка ...

Опытный

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

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

Не в обиду будет сказано, но у тебя в коде чёрт ногу сломит + пользуйся подсветкой когда выкладываешь исходники smile

. Бинарный поиск по своему определению подразумевает, что у тебя один искомый элемент. Конечно можно доработать чтобы искал все эелементы, но на мой взгляд для твоей лабораторной это не нужно. Вот твой код, только немного переделанный мною:

Код


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main (int argc, char **argv)
{
   int i, j, el, m, k, kol= 0, w, last, first, mid, row, col, **ar;
   srand (time (0));

   printf ("row col> ");
   scanf ("%d%d", &row, &col);
   printf ("\n-----\nMatrix:\n");

   ar= malloc (sizeof (int *) * row);
   for (i= 0; i < row; i++)
   {
      ar[i]= malloc (sizeof (int) * col);
      for (j= 0; j < col; j++)
      {
         ar[i][j]= rand () % 99;
         printf ("%2d ", ar[i][j]);
      }
      printf ("\n");
   }

// Sorting by selection
   for (j= 0; j < col; j++)
      for (m= 0; m < row - 1; m++)
         for (i= m + 1; i < row; i++)
         {               
            if (ar[i][j] < ar[m][j])
            {    
                w= ar[m][j];
                ar[m][j]= ar[i][j];
                ar[i][j]= w;
            }
         }

   printf("\n-----\nSorting by selection:\n");
   for (i= 0; i < row; i++)
   {
      for (j= 0; j < col; j++)
         printf ("%2d ", ar[i][j]);
      printf("\n");
   }    

   printf ("\nFind elemet: ");
   scanf ("%d", &el);

// Consecutive search    
   printf("\n-----\nConsecutive search:\n");
   for (j= 1; j < col; j+=2)
   {
      for (i= 0; i < row; i++)
      {
         if (ar[i][j] == el)
         {
            kol++;
            printf("col %2d in row %2d\n", j + 1, i + 1);
         }
      }
   }    
   if (kol == 0)
      printf("Not found\n");    

// Binary search
   printf ("\nBinary search:\n");
   for (j= 0; j < col; j+= 2)
   {
      first= 0;
      last= row - 1;
      while (first <= last)
      {

         mid= (first + last) / 2;
         if (ar[mid][j] < el)
            first= mid + 1;
         else if (ar[mid][j] > el)
            last= mid - 1;
         else
         {
            kol++;
            printf ("col %2d in row %2d\n", j + 1, mid + 1);
            break;
         }
      }
   }
   if (kol == 0)    
      printf("Not found\n");    
   return 0;    
}

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

Я знаю, что ничего не знаю© Сократ
user posted image

vorovaika

Дата 15.5.2008, 19:26 (ссылка)

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

Загрузка ...

Новичок

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

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

спасибо. а Вы не подскажете, как сделать,ч тобы он искал не только этот элемент, а еще и последовательность(до трёх вводимых элементов)?

t_gran

Дата 16.5.2008, 03:17 (ссылка)

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

Загрузка ...

Опытный

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

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

Вот, теперь будет все элементы искать. smile

Код


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main (int argc, char **argv)
{
   int i, j, el, m, k, kol= 0, w, last, first, mid, row, col, **ar;
   srand (time (0));

   printf ("row col> ");
   scanf ("%d%d", &row, &col);
   printf ("\n-----\nMatrix:\n");

   ar= malloc (sizeof (int *) * row);
   for (i= 0; i < row; i++)
   {
      ar[i]= malloc (sizeof (int) * col);
      for (j= 0; j < col; j++)
      {
         ar[i][j]= rand () % 99;
         printf ("%2d ", ar[i][j]);
      }
      printf ("\n");
   }

// Sorting by selection
   for (j= 0; j < col; j++)
      for (m= 0; m < row - 1; m++)
         for (i= m + 1; i < row; i++)
         {               
            if (ar[i][j] < ar[m][j])
            {    
                w= ar[m][j];
                ar[m][j]= ar[i][j];
                ar[i][j]= w;
            }
         }

   printf("\n-----\nSorting by selection:\n");
   for (i= 0; i < row; i++)
   {
      for (j= 0; j < col; j++)
         printf ("%2d ", ar[i][j]);
      printf("\n");
   }    

   printf ("\nFind elemet: ");
   scanf ("%d", &el);

// Consecutive search    
   printf("\n-----\nConsecutive search:\n");
   for (j= 1; j < col; j+=2)
   {
      for (i= 0; i < row; i++)
      {
         if (ar[i][j] == el)
         {
            kol++;
            printf("col %2d in row %2d\n", j + 1, i + 1);
         }
      }
   }    
   if (kol == 0)
      printf("Not found\n");    

// Binary search
   printf ("\nBinary search:\n");
   for (j= 0; j < col; j+= 2)
   {
      first= 0;
      last= row - 1;
      while (first <= last)
      {

         mid= (first + last) / 2;
         if (ar[mid][j] < el)
            first= mid + 1;
         else if (ar[mid][j] > el)
            last= mid - 1;
         else
         {
            kol++;
            int buf= mid;
            while (buf > 0 && ar[--buf][j] == el);
            while (++buf < row && ar[buf][j] == el)
               printf ("col %2d in row %2d\n", j + 1, buf + 1);
            break;
         }
      }
   }
   if (kol == 0)    
      printf("Not found\n");    
   return 0;    
}

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

vorovaika

Дата 16.5.2008, 06:44 (ссылка)

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

Загрузка ...

Новичок

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

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

спасибо огромное !

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