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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
#1

Нужен алгоритмом по вставлению числа в массив - C++

17.06.2012, 03:16. Просмотров 1086. Ответов 27
Метки нет (Все метки)

Помогите...
Дана последовательность действительный чисел A1 <= A2, <= ... An. Вставить действительно число b в неё так, чтобы последовательность осталась неубывающей.
Есть код. Нужен сам алгоритм по вставлению числа в массив. Уже несколько дней пытаюсь найти ответ.

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
#include <iostream>
using namespace std;
 
int main()
{
   int n, a[n], b; 
    cout << "Введите количество элементов в массиве" << endl;
   cin >> n;
    cout << "Введите b" << endl;
   cin >> b;
    cout << "Введите значение элементов" << endl;
   for (int i = 0; i < n; i++)
    cin >> a[i]; 
   for (int i = 0; i < n; i++)  
    cout << a[i] << " ";
   for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) 
     while (a[i] > a[j])
     { 
       cout << "Введите значения последовательно" << endl;
       for (int i = 0; i < n; i++)
       cin >> a[i];
     }
    cout << endl;
    // алгоритм вставки
    
system("PAUSE >> null");    
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2012, 03:16     Нужен алгоритмом по вставлению числа в массив
Посмотрите здесь:

C++ Задан вектор X[20]. Положительные числа переписать в массив Y, а отрицательные в массив W
Дан массив В[0:n-1] целых чисел и числа x и y , где x<y. на основе элементов массива В сформировать массив D[0:m-1] C++
C++ Задан вектор X[20]. Положительные числа переписать в массив Y, а отрицательные в массив W
C++ нужен тип целого числа для числа 19!= 121 645 100 408 832 000
C++ Конвертор десятичного числа в шестнадцатиричное с алгоритмом преобразования
C++ Одномерный массив. Вывести на экран все числа, индексы которых есть простые числа.
C++ Массив: Переместить в массив Y все числа, дробная часть которых больше 5.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
blits
2 / 2 / 0
Регистрация: 06.02.2012
Сообщений: 33
17.06.2012, 03:30     Нужен алгоритмом по вставлению числа в массив #2
C
1
2
3
4
5
6
7
8
for (int i = 0; i < n; i++)
      for (int j = i; j < n; j++)
            while (a[i] > a[j])
            {
                  cout << "Введите значения последовательно" << endl;
                  for (int i = 0; i < n; i++)
                         cin >> a[i];
            }
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
17.06.2012, 03:33  [ТС]     Нужен алгоритмом по вставлению числа в массив #3
Что такое?
blits
2 / 2 / 0
Регистрация: 06.02.2012
Сообщений: 33
17.06.2012, 03:40     Нужен алгоритмом по вставлению числа в массив #4
как-то пугает 4-х кратный цикл)))
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
17.06.2012, 03:49  [ТС]     Нужен алгоритмом по вставлению числа в массив #5
Я более чем уверен, что есть способ легче, но при тестировании работает. Да и знаний пока что не достаточно чтобы сделать по-другому.
Avazart
7062 / 5239 / 261
Регистрация: 10.12.2010
Сообщений: 23,037
Записей в блоге: 17
17.06.2012, 04:58     Нужен алгоритмом по вставлению числа в массив #6
Цитата Сообщение от Leonman Посмотреть сообщение
алгоритм по вставлению числа в массив
Такое нельзя реализовать непосредственно...

Используй std::vector либо другой контейнер, в противном случае придеться работать с динамическими массивами
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
17.06.2012, 06:31  [ТС]     Нужен алгоритмом по вставлению числа в массив #7
С vector у меня совсем дела плохи, да и с динамическими не разобрался, даже матриц ещё не брал. Программирую только 2 месяца, да и то я программист самоучка. В моём возросте особо некуда пойти учиться.
Неужели нельзя вставку произвести используя только одномерный массив. Задание то само относить в раздел "одномерные массивы"
soon
2537 / 1302 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
17.06.2012, 06:52     Нужен алгоритмом по вставлению числа в массив #8
Leonman, Никак. Разве что выделить больше и фальсифицировать конец массива. Изучайте динамику.
dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
17.06.2012, 10:40     Нужен алгоритмом по вставлению числа в массив #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
#include "stdafx.h"
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale (0,"Russian");
    const int n = 1000;
    int arr[n], b;
    //формируем последовательность
    for (int i= 1; i<n+1; i ++) 
        arr[i-1]= i;
 
    //вводим число
    cout <<"Введите число от 1 до "<<n <<" ";
    cin >> b;
 
    //создаем итоговый массив для последовательности + введенное число
    int arrRezault[n+1]; 
 
    // заполняем итоговый массив
    bool valueInserted = false;
    for (int i= 0; i<n+1; i ++)
    {
        if (arr[i] <= b)
        {
            arrRezault[i] = arr[i];
        }
        else
        {
            if (!valueInserted)
            {
                valueInserted=true;
                arrRezault[i] = b;
                
            }
            arrRezault[i+1] = arr[i];
        }
    }
 
    return 0;
}
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
17.06.2012, 13:05  [ТС]     Нужен алгоритмом по вставлению числа в массив #10
dima koz, Огромное спасибо! Всё работает. Только вопрос, почему когда я например вставляю число 5 в последовательность из 10 элементов {1,2,3,4,6,7,8,9,10,11}, то у меня последний элемент заменяется на -1?

Добавлено через 25 секунд
soon, Обезательно изучу
dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
17.06.2012, 15:21     Нужен алгоритмом по вставлению числа в массив #11
Цитата Сообщение от Leonman Посмотреть сообщение
Только вопрос, почему когда я например вставляю число 5 в последовательность из 10 элементов {1,2,3,4,6,7,8,9,10,11}, то у меня последний элемент заменяется на -1?
сорри, в 24 строке заменить надо на:
C++
1
 for (int i= 0; i<n; i ++)
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
18.06.2012, 15:11  [ТС]     Нужен алгоритмом по вставлению числа в массив #12
dima koz, Тогда если я например вставляю число 11 в последовательность из 10 элементов {1,2,3,4,5,6,7,8,9,10}, то у меня последний элемент заменяется на 3?
dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
18.06.2012, 23:03     Нужен алгоритмом по вставлению числа в массив #13
Цитата Сообщение от Leonman Посмотреть сообщение
dima koz, Тогда если я например вставляю число 11 в последовательность из 10 элементов {1,2,3,4,5,6,7,8,9,10}, то у меня последний элемент заменяется на 3?
хороший тестер из вас
крайние значения проверили, теперь так выглядит код:
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
#include "stdafx.h"
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale (0,"Russian");
    const int n = 10;
    int arr[n] , b;
    ////формируем последовательность
    for (int i= 1; i<n+1; i ++) 
        arr[i-1]= i;
 
    //вводим число
    cout <<"Введите число от 1 до "<<n <<" ";
    cin >> b;
 
    //создаем итоговый массив для последовательности + введенное число
    int arrRezault[n+1]; 
 
    // заполняем итоговый массив
    bool valueInserted = false;
    for (int i= 0; i<n; i ++)
    {
        if (arr[i] < b)
        {
            arrRezault[i] = arr[i];
            if (i+1 == n) arrRezault[i+1] = b;
        }
        else
        {
            if (!valueInserted)
            {
                valueInserted=true;
                arrRezault[i] = b;
            }
 
            arrRezault[i+1] = arr[i];
        }
    }
 
    return 0;
}
Avazart
7062 / 5239 / 261
Регистрация: 10.12.2010
Сообщений: 23,037
Записей в блоге: 17
19.06.2012, 00:35     Нужен алгоритмом по вставлению числа в массив #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
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
#include <iostream>
using namespace std;
//----------------------------------------------------------
void insert(int * &Array,int& size,int value,int pos)
{
 int* NewArray= new int[size+1]; 
 
 NewArray[pos]=value;  
 
 for(int i=0,k=0;i<size;k++)
  {
    if(k == pos) continue;
    NewArray[k]= Array[i]; 
    i++;
  } 
 
 delete[] Array; 
 Array= NewArray;
 size++;
}
//----------------------------------------------------------
void print(int A[],const int& size)
{
 cout<<"Значения элементов массива :"<<endl;
 for(int i=0;i<size;i++) cout<<A[i]<<" ";
 cout<<endl;
}
//----------------------------------------------------------
void input(int A[],const int& size)
{
 cout<<"Введите значения элементов массива"<<endl; 
 cin.sync();
 for(int i=0;i<size;i++) cin>>A[i];
}
//----------------------------------------------------------
int main()
{
int size;
cout<<"Введите начальный размер массив"<<endl; cin.sync();
cin>>size;
 
int *A = new int[size];
 
input(A,size);
print(A,size);
 
for(;;)
 { 
  int value,pos;
 
   cout<<"Введите значение вставляемого элемента ";  cin.sync();
   cin>>value;
   cout<<"Введите положение вставляемого элемента ";  cin.sync();
   cin>>pos;
  
   insert(A,size,value,pos);
   print(A,size);
 }
 
delete[] A;
return 0;
}//----------------------------------------------------------------
LittleGirl
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 5
19.06.2012, 00:54     Нужен алгоритмом по вставлению числа в массив #15
-1 получается потому, что цикл для заполнения итогового массива до i<n+1. Внутри цикла вычисляется значение arr[i], то есть на последнем шаге цикла имеем arr[n]. А по этому адресу лежит всякий мусор, в вашем случае там лежала -1. Это значение сравнилось с b=5, мы попали в if и получили arrRezault[n] = arr[n], т.е. последнее значение в итоговом массиве заменили на эту самую -1.
Если цикл сделать до i<n то 5 вставляется хорошо. Но вот если попробовать вставить, например, 15, то мы никогда не зайдем в else и не инициализируем последний элемент массива arrRezault, в итоге опять получим там всё что угодно.

Мой вариант:
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
#include "stdafx.h"
#include "locale.h"
#include "iostream"
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale (0,"Russian");
    const int n = 10;
    int arr[n], b;
    //формируем последовательность
    for (int i= 1; i<n+1; i ++) 
        arr[i-1]= i;
 
    //вводим число
    cout <<"Введите число от 1 до "<<n <<" ";
    cin >> b;
    //создаем итоговый массив для последовательности + введенное число
    int arr_rez[n+1]; 
 
    int i, ind=n;
    // Ищем индекс элемента, большего чем b
    for(i=0;i<n;i++)
        if (arr[i]>b) {ind=i; break;}
 
    // копируем всё до ind
    for(i=0;i<ind;i++)
        arr_rez[i]=arr[i];
 
    // вставляем b
    arr_rez[ind]=b;
 
    // копируем оставшееся
    for(i=ind+1;i<n+1;i++)
        arr_rez[i]=arr[i-1];
 
    return 0;
}
Avazart
7062 / 5239 / 261
Регистрация: 10.12.2010
Сообщений: 23,037
Записей в блоге: 17
19.06.2012, 01:01     Нужен алгоритмом по вставлению числа в массив #16
Как я понял последние элементы в массиве должны теряться после вставки?
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,989
19.06.2012, 01:19     Нужен алгоритмом по вставлению числа в массив #17
Цитата Сообщение от Avazart Посмотреть сообщение
Как я понял последние элементы в массиве должны теряться после вставки?
Зачем теряться? Между прочим, в самом задании про массивы ни слова. Там последовательность. Почему размер массива, хранящего последовательность, обязательно должен быть равен длине последовательности мне совершенно не понятно.
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
19.06.2012, 01:30  [ТС]     Нужен алгоритмом по вставлению числа в массив #18
dima koz, Спасибо огромное. Протестил все варианты, всё работает.

Добавлено через 1 минуту
Avazart, Пока что с моими знаниями я не могу до конца разобрать ваш код, но всё равно спасибо.
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,989
19.06.2012, 01:33     Нужен алгоритмом по вставлению числа в массив #19
Ну и ещё один
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
#include <iostream>
 
using namespace std;
 
int main()
{
    const unsigned ARRAY_SIZE = 100;
    unsigned n;
    int a[ARRAY_SIZE], b; 
    do {
        cout << "Введите количество элементов в массиве от 1 до " << ARRAY_SIZE-1 << endl;
        if (!(cin >> n))
        {
            cerr << "FATAL: Input error" << endl;
            return 1;
        }
    } while (n < 1 || n >= ARRAY_SIZE);
    
    cout << "Введите b" << endl;
    cin >> b;
 
    cout << "Введите значение элементов" << endl;
    for (unsigned i = 0; i < n; i++)
        cin >> a[i]; 
    cout << endl;
 
    if (!cin)
    {
        cerr << "FATAL: Input error" << endl;
        return 1;
    }
 
    // алгоритм вставки
    unsigned idx = n;
    for (; idx > 0 && a[idx-1] > b; --idx)
        a[idx] = a[idx-1];
    a[idx] = b;
 
    cout << "New sequence:\n";
    for (unsigned i = 0; i <= n; i++)
        cout << a[i] << ' ';
    cout << endl; 
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2012, 01:46     Нужен алгоритмом по вставлению числа в массив
Еще ссылки по теме:

C++ Рекурсия (функция определения НОД (наибольшего общего делителя) числа алгоритмом Евклида)
Переписать числа в массив Z по условию. Удалить все нечетные числа C++
C++ Массив A содержит только два одинаковых числа. Найти эти числа и указать их индексы ошибка
C++ Перенести в один другой массив четные числа.Затем перенести в еще один другой массив нечетные числа.

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

Или воспользуйтесь поиском по форуму:
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
19.06.2012, 01:46  [ТС]     Нужен алгоритмом по вставлению числа в массив #20
LittleGirl, Всё работает, но опять же до того момента, когда я пытаюсь вставить 11 в последовательность arr[10] = {1,2,3,4,5,6,7,8,9,10}. В итоге 11 стоит между 2 и 3.
Спасибо за код

Добавлено через 4 минуты
grizlik78, Да тоже абсолютно работающий код. Спасибо!
Yandex
Объявления
19.06.2012, 01:46     Нужен алгоритмом по вставлению числа в массив
Ответ Создать тему
Опции темы

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