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

бинарные вставки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
edward_jonson
 Аватар для edward_jonson
157 / 157 / 25
Регистрация: 23.02.2011
Сообщений: 388
02.03.2011, 22:07     бинарные вставки #1
укажите на ошибку пожалуйста!
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
 stroka1[0]=stroka2[0];
 for (h=1;h<=k;h++)
 {
    if (stroka1[h]>=stroka2[h-1])
   R=h;
    else
    {
        if (stroka1[h]<stroka2[1])
        R=1;
        else
        {
            L=1;
            R=h-1;
            while(R-L>1)
            {
                M=(R+L)/2;
                if (stroka2[M]<stroka1[h])
                L=M;
                else
                R=M;
            }
         }
 
      for (t=h;t>R;t--)
       {
         stroka2[t]=stroka1[t-1];
       }
 
   }
   stroka2[R]=stroka1[h];
 }
в данном случае сортируем бинарными вставками массив stroka1 и записываем в stroka2, выводит только часть чисел и набор лишних цифр

Добавлено через 20 часов 16 минут
EDIT:
C++
1
stroka2[0]=stroka1[0]
и в 9-ой строке
C++
1
if stroka1[h]<stroka2[0]
сортирует, но неправильно всё равно
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.03.2011, 22:07     бинарные вставки
Посмотрите здесь:

C++ С++ бинарные файлы
C++ бинарные деревья
Бинарные деревья C++
Бинарные файлы C++
Бинарные деревья C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
03.03.2011, 04:18     бинарные вставки #2
C++
1
for (h=1;h<=k;h++)
чему равно k ?
edward_jonson
 Аватар для edward_jonson
157 / 157 / 25
Регистрация: 23.02.2011
Сообщений: 388
03.03.2011, 17:10  [ТС]     бинарные вставки #3
Цитата Сообщение от accept Посмотреть сообщение
C++
1
for (h=1;h<=k;h++)
чему равно k ?
k=m*n;
m и n это размерность двумерного динамического массива, который я переписал в строку, которую пытаюсь отсортировать, но не получается
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
04.03.2011, 01:57     бинарные вставки #4
C++
1
for (h = 1; h < k; h++)
edward_jonson
 Аватар для edward_jonson
157 / 157 / 25
Регистрация: 23.02.2011
Сообщений: 388
04.03.2011, 20:52  [ТС]     бинарные вставки #5
всё равно коряво сортирует (
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
05.03.2011, 02:09     бинарные вставки #6
код неполный, запости всю функцию
edward_jonson
 Аватар для edward_jonson
157 / 157 / 25
Регистрация: 23.02.2011
Сообщений: 388
05.03.2011, 13:32  [ТС]     бинарные вставки #7
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
102
103
104
105
106
107
108
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
void main(){
int i,j,m,n,k,h,t, **mas,**mass,*stroka1,*stroka2, L, M, R;
   printf("Vvedite kolichestvo strok: ");
   scanf("%d",&m);
   printf("Vvedite kolichestvo stolbcov: ");
   scanf("%d",&n);
     mas=(int**)malloc(m*sizeof(int*));
    for(i=0;i<m;i++)
    mas[i]=(int*)malloc(n*sizeof(int));
    mass=(int**)malloc(m*sizeof(int*));
    for(i=0;i<m;i++)
    mass[i]=(int*)malloc(n*sizeof(int));
    stroka1=(int*)malloc(m*n*sizeof(int));
    stroka2=(int*)malloc(m*n*sizeof(int));
   printf("Vvedite elementi massiva:\n")     ;
    for(i=0;i<m;i++)
   {
    for(j=0;j<n;j++)
    scanf("%d",&mas[i][j]);
   }
 printf("Massiv do sortirovki:\n");
    for(i=0;i<m;i++)
  {
   for(j=0;j<n;j++)
   printf("%3d",mas[i][j]);
   printf("\n");
  }
 
   k=m*n;
   for(h=0;h<k;h++)
   {
    for(i=0;i<m;i++)
    {
     for(j=0;j<n;j++)
     {
      stroka1[h]=mas[i][j];
      h++;
     }
    }
   }
/* переписал массив в строку для более удобной сортировки */
   printf ("stroka pered sortirovkoy:\n");
   for (h=0;h<k;h++)
   {
      printf ("%3d",stroka1[h]);
   }
 
 printf ("\n");
 
 stroka2[0]=stroka1[0];
 for (h=1;h<k;h++)
 {
    if (stroka1[h]>=stroka2[h-1])
   R=h;
    else
    {
        if (stroka1[h]<stroka2[0])
        R=0;
        else
        {
            L=0;
            R=h;
            while(R-L>1)
            {
                M=(R+L)/2;
                if (stroka2[M]<stroka1[h])
                L=M;
                else
                R=M;
            }
         }
 
      for (t=h;t>R;t--)
       {
         stroka2[t]=stroka1[t-1];
       }
 
   }
   stroka2[R]=stroka1[h];
 }
 printf ("stroka posle sortirovki:\n");
  for (h=0;h<k;h++)
   {
      printf ("%3d",stroka2[h]);
    }
      for (h=0;h<k;h++){
     for(i=0;i<m;i++){
      for (j=0;j<n;j++){
       mas[i][j]=stroka2[h];
       h++;
              }
         }
}
/*переписал строку в массив для вывода*/
   printf ("\n");
   printf ("massiv posle sortirovki:\n");
   for(i=0;i<m;i++)
  {
   for(j=0;j<n;j++)
   printf("%3d",mas[i][j]);
   printf("\n");
 }
getch();
}
   }
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.03.2011, 04:24     бинарные вставки #8
C++
1
2
3
4
5
6
     mas=(int**)malloc(m*sizeof(int*));
    for(i=0;i<m;i++)
    mas[i]=(int*)malloc(n*sizeof(int));
    mass=(int**)malloc(m*sizeof(int*));
    for(i=0;i<m;i++)
    mass[i]=(int*)malloc(n*sizeof(int));
ошибка, повторяется одно и то же

C++
1
2
3
4
5
for(j=0;j<n;j++)
     {
      stroka1[h]=mas[i][j];
      h++;
     }
ошибка, наращивается h, которое и так наращивается в первом цикле

что-то не понятно, зачем тебе по три цикла
C++
1
2
3
      for (h=0;h<k;h++){
     for(i=0;i<m;i++){
      for (j=0;j<n;j++){
это что ?
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
stroka2[0]=stroka1[0];
 for (h=1;h<k;h++)
 {
        if (stroka1[h]>=stroka2[h-1])
   R=h;
        else
        {
                if (stroka1[h]<stroka2[0])
        R=0;
        else
        {
                L=0;
                R=h;
                while(R-L>1)
                {
                        M=(R+L)/2;
                if (stroka2[M]<stroka1[h])
                L=M;
                else
                R=M;
                }
         }
 
      for (t=h;t>R;t--)
       {
         stroka2[t]=stroka1[t-1];
       }
 
   }
   stroka2[R]=stroka1[h];
 }


Добавлено через 7 минут
intuit. бинарные вставки

Код
Реализация алгоритма БинВст

for i:= 2 to n do
    if a[i-1]>a[i] then
    begin
        x:= a[i];
	left:= 1;
	right:= i-1;
	repeat
	    sred:= (left+right)div 2;
	    if a[sred]<x then
                left:= sred+1
            else
                right:= sred-1;
	until left>right;
	for j:= i-1 downto left do
            a[j+1]:= a[j];
	a[left]:= x;
    end;
edward_jonson
 Аватар для edward_jonson
157 / 157 / 25
Регистрация: 23.02.2011
Сообщений: 388
06.03.2011, 17:08  [ТС]     бинарные вставки #9
не одно и то же, я 2 динамических массива использую, он в другой части программы требуется, h наращивается специально, чтобы не возвращаться к его обнулению, т.к. тогда строка будет заполнена последним элементом массива, с тремя циклами всё работает, как раз с этим всем проблем нет, проблема в реализации сортировки
edward_jonson
 Аватар для edward_jonson
157 / 157 / 25
Регистрация: 23.02.2011
Сообщений: 388
07.03.2011, 20:59  [ТС]     бинарные вставки #10
нужна помощь!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.03.2011, 04:30     бинарные вставки
Еще ссылки по теме:

C++ Бинарные файлы
Бинарные файлы C++
C++ Бинарные деревья

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

Или воспользуйтесь поиском по форуму:
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
09.03.2011, 04:30     бинарные вставки #11
сортировка бинарными вставками
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
 
#include <stdio.h>
 
enum { N = 8 };
 
void print(int arr[], size_t n,
           const char *sep, const char *end);
void bin_ins_sort(int arr[], int n);
 
/* сортировка бинарными вставками */
int main(void)
{
    int n[N] = { 4, 3, 9, 8, 7, 8, 2, 1 };
    
    print(n, N, NULL, NULL);
    bin_ins_sort(n, N);
    print(n, N, NULL, NULL);
    return 0;
}
 
/* выводит массив целых чисел */
void print(int arr[], size_t n,
           const char *sep, const char *end)
{
    if (!sep)
        sep = ", ";
    if (!end)
        end = "\n";
    for ( ; n > 0; n--)
        printf("%d%s", *arr++, n - 1 != 0 ? sep : end);
}
 
/* сортирует массив целых чисел бинарными вставками */
void bin_ins_sort(int arr[], int n)
{
    int i, j, x, left, right, mid;
    
    for (i = 1; i < n; i++)
        if (arr[i - 1] > arr[i]) {
            x = arr[i];
            left = 0;
            right = i - 1;
            while (left <= right) {
                mid = (left + right) / 2;
                if (arr[mid] < x)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            for (j = i - 1; j >= left; j--)
                arr[j + 1] = arr[j];
            arr[left] = x;
        }
}
 
/*
 
Реализация алгоритма БинВст
 
for i:= 2 to n do
    if a[i-1]>a[i] then
    begin
        x:= a[i];
        left:= 1;
        right:= i-1;
        repeat
            sred:= (left+right)div 2;
            if a[sred]<x then
                left:= sred+1
            else
                right:= sred-1;
        until left>right;
        for j:= i-1 downto left do
            a[j+1]:= a[j];
        a[left]:= x;
    end;
    
*/
Код
[guest@localhost tests]$ ./t
4, 3, 9, 8, 7, 8, 2, 1
1, 2, 3, 4, 7, 8, 8, 9
[guest@localhost tests]$

там описание одно (на интуите), а алгоритм этот вообще другой
(по описанию нужно складывать концы массива, а в алгоритме складываются концы подмассива)
Yandex
Объявления
09.03.2011, 04:30     бинарные вставки
Ответ Создать тему
Опции темы

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