Форум программистов, компьютерный форум CyberForum.ru

Ввести число и найти в массиве ближайшее к нему методом двоичного поиска - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.65
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
24.03.2011, 20:03     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #1
Ввести массив целых чисел и отсортировать его ( можно использовать qsort).Ввести число и найти в массиве ближайшее к нему методом двоичного поиска.

На языке Си.
Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2011, 20:03     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска
Посмотрите здесь:

C++ Найти ближайшее к введенному числу простое число
C++ Дано натуральное число. Найти ближайшее простое число
C++ В массиве вещественных чисел найти ближайшее к какому-нибудь целому.
Найти ближайшее справа число, которое является квадратом натурального числа C++
Найти ближайшее к данному число, которое делится на 3, но не делится на 2. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bebedor
3 / 3 / 0
Регистрация: 14.02.2011
Сообщений: 9
24.03.2011, 21:25     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #2
Держи, создание, сортировка(пузырьком) мои, поиск взят с википедии
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <vcl.h>
#pragma hdrstop
#pragma argsused
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define obmen(a, b) {int c=a; a=b; b=c;}
int scanf_err ()    
{
    int n;  
    char err[250];
    while (!scanf("%d",&n))
    {
    scanf("%s",err);
    printf("error\nvvedite zanovo\n>");
    }
    return n;
}
int main(int argc, char* argv[])
{
    int a, i, h;
                
    char err[250];
    do
    {
    clrscr();   
    do
        {
        printf("Vvedite kol-vo elementov massiva=>");
        a=scanf_err();  
        if (a<1)    
            {
            printf("Vvedite chislo bolshe 0\n");
            }
        }
        while (a<1);    
    int *mass=(int*)malloc(a*sizeof(int));
    for (i=0; i<a; i++) 
        {
        mass[i]=rand()%100; 
        }
    
    printf("\nIshodnii massiv  ");
        for (i=0; i<a; i++) 
        {
        printf("%d", mass[i]);
        printf(" ");
        }
    
    
    for (i=a-1; i>0; i--)
  {
    for (h=0; h<i; h++)
    {
      if (mass[h]>mass[h+1])
        obmen(mass[h], mass[h+1]);
    }
  }
    int f;
    printf("\nVvedite chislo=>");
    scanf("%d", &f);
    size_t first = 0; /* Первый элемент в массиве */
    size_t last = a;  /* Элемент в массиве, СЛЕДУЮЩИЙ ЗА последним */
                    /* Если просматриваемый участок непустой, first<last */
    size_t mid; 
 
  if (a==0) {
     /* массив пуст */
  } else if (mass[0]>f) {
     /* не найдено; если вам надо вставить его со сдвигом - то в позицию 0  */
  } else if (mass[a-1]<f) {
     /* не найдено; если вам надо вставить его со сдвигом - то в позицию n  */
  }
 
  while ( first < last ) {
    /* ВНИМАНИЕ! В отличие от более простого (first+last)/2, этот код стоек к переполнениям.  */
    mid = first + (last-first)/2;
 
    if ( f <= mass[mid] ) {
      last = mid;
    } else {
      first = mid + 1;
    }
  }
 
  /* Если проверка n==0 в начале опущена - значит, тут раскомментировать!  */
  if (/*n!=0 &&*/ mass[last] == f) {
    /* Искомый элемент найден. last - искомый индекс */
  } else {
    /* Искомый элемент не найден. Но если вам вдруг надо его вставить со сдвигом, то его место - last.  */
  }
    
    printf("%d", mass[last]);
    free(mass); 
    printf("\n\nSnachala?\n\n1-DA\n2-NET\n>");  
    }
    while(scanf_err()!=2);
 
    return 0;
}
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
27.03.2011, 11:19  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #3
а можно как нибудь по проше и без работы с консолью?*
bbo0ss
1 / 1 / 0
Регистрация: 23.03.2011
Сообщений: 19
27.03.2011, 11:25     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #4
C++
1
#define obmen(a, b) {int c=a; a=b; b=c;}
если бы он сам понял че тут написал))) О_О
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
31.03.2011, 19:29  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #5
UP =//
ViZ3R
0 / 0 / 0
Регистрация: 20.03.2011
Сообщений: 4
31.03.2011, 20:08     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #6
это сортировка
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <locale>
#include <cstdlib>
using namespace std;
 
void main()
{
setlocale (LC_ALL, "Russian");
srand((unsigned)time( NULL ));
int size;
int i,j,q;
cout<<"введите размерность массива"<<endl;
cin>>size; 
int *mas;/
mas=new int[size];
for(i=0;i<size;i++)
{
mas[i]=rand()%2000-1000; //от -1000 до 1000 
}
cout<<"Исходный массив"<<endl;
for(i=0;i<size;i++) 
{
cout<<mas[i]<<" ";
}
for(i=1;i<size;i++)//сортировка пузырьком
{
 for(j=size-1;j>=i;j--)
 {
    if(mas[j-1]>mas[j]) 
    {
    q=mas[j-1];
    mas[j-1]=mas[j];
    mas[j]=q;
    }
 }
}
 cout<<endl<<"Упорядоченный массив"<<endl;
 for(i=0;i<size;i++) cout<<mas[i]<<" ";
 delete[] mas;
_getch();
 
}
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
31.03.2011, 22:56  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #7
Цитата Сообщение от Оленька* Посмотреть сообщение
На языке Си.
(((((
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
03.04.2011, 21:45  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #8
UP!!!!
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
05.04.2011, 15:04  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #9
Help=//
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
09.04.2011, 21:53  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #10
Up////
vitaska
 Аватар для vitaska
83 / 83 / 2
Регистрация: 04.02.2010
Сообщений: 162
09.04.2011, 22:29     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #11
что значит ближайшее? то которое слева от него или справа? либо же ближайшее меньшее или ближайшее большее? уточните

Добавлено через 9 минут
Вот пока что есть, если уточните какое число именно мы ищем, то можно подправить будет
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
 
#define SIZE 15
//Быстрая сортировка
void quickSortR(int a[], int B, int E)
{
    long i = B, j = E;
    int temp, p;
    p = a[(B+E)/2];
    do{
        while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
        if (i <= j){
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }while ( i<=j );
    if(B<j)quickSortR(a, B, j);
    if(i<E)quickSortR(a, i, E);
}
//Двоичный поиск
int BinarySearch (int A[], int Lb, int Ub, int Key)
{
    int M;
    while(1){
        M = (Lb + Ub)/2;
        if (Key < A[M])
            Ub = M - 1;
        else if (Key > A[M])
            Lb = M + 1;
        else
            return M;
 
        if (Lb > Ub)
            return -1;
    }
}
 
int main()
{
    srand( ( unsigned ) time ( NULL ) );
    int arr[ SIZE ];
    int i, key, index;
 
    // до сортировки
    for( i = 0; i < SIZE; i++ ){
        arr[ i ] = rand() % 100;
        printf( "%d ", arr[ i ] );
    }
    printf( "\n\n" );
    quickSortR( arr, 0, SIZE - 1 );
 
    printf( "Input number: " );
    scanf( "%d", &key );
//тут используем функцию двоичного поиска
//в зависимости от того что нужно найти
    index = BinarySearch(arr,0,SIZE,key);
 
    // после сортировки
    for( i = 0; i < SIZE; i++ ){
        printf( "%d ", arr[ i ] );
    }
    printf( "\n\n" );
 
    return 0;
}
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
10.04.2011, 09:57  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #12
большое))
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
14.04.2011, 18:01  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #13
АП!!!

Добавлено через 4 часа 43 минуты
UP!!!
igorrr37
 Аватар для igorrr37
1593 / 1221 / 118
Регистрация: 21.12.2010
Сообщений: 1,868
Записей в блоге: 7
14.04.2011, 19:49     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #14
ищет ближайшее по абсолюту
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<math.h>
 
int Compare(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}
 
int BSearch (int A[], int Lb, int Ub, int Key){
    int M;
    while(1){
        M = (Lb + Ub)/2;
        if (Key < A[M]){
            Ub = M - 1;
        }
        else if (Key > A[M]){
            Lb = M + 1;
        }
        else{
            return M;
        }
        if (Lb > Ub){
            return fabs(A[Lb]-Key)<fabs(A[Ub]-Key)? Lb: Ub;
        }
    }
}
 
int main(){
    int arr[]={-20,50,-10,0,10,20,-30,30,40}, size=sizeof(arr)/sizeof(*arr), key=23, i;
    qsort(arr, size, sizeof(*arr), Compare);
    puts("Sorted array:");
    for(i=0; i<size; i++){
        printf("%d ", arr[i]);
    }
    int index=BSearch(arr, 0, size, key);
    printf("\n\nNearest number: %d", arr[index]);
    return 0;
}
Настьона
 Аватар для Настьона
1 / 1 / 0
Регистрация: 29.05.2010
Сообщений: 57
14.04.2011, 22:25     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #15
Помогите,пожалуйста,со второй задачей:
ПЕРЕГРУЗКА ОПЕРАЦИЙ
Спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2011, 19:04     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска
Еще ссылки по теме:

C++ Найти ближайшее число,которое делится на 3, но не делится на 2
Найти число, получаемое из исходного приписыванием к нему такого же числа C++
C++ Найти ближайшее число

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Оленька*
2 / 2 / 0
Регистрация: 15.12.2010
Сообщений: 58
28.04.2011, 19:04  [ТС]     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска #16
Двоичный поиск не работает...

Добавлено через 9 часов 24 минуты
UP!!!

Добавлено через 18 часов 58 минут
Up////

Добавлено через 23 часа 22 минуты
помогите с двоичным поиском

Добавлено через 21 час 29 минут
UP!!!//(

Добавлено через 6 часов 38 минут
UP(((

Добавлено через 21 час 47 минут
up.......
Yandex
Объявления
28.04.2011, 19:04     Ввести число и найти в массиве ближайшее к нему методом двоичного поиска
Ответ Создать тему
Опции темы

Текущее время: 16:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru