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

Выяснить, сколько чисел входит в последовательность по одному разу - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.74
Glam_Man
6 / 6 / 0
Регистрация: 15.10.2011
Сообщений: 73
29.10.2011, 16:54     Выяснить, сколько чисел входит в последовательность по одному разу #1
Условие задачи написано в шапке кода программы. Я написал эту программу, программа работает. Но есть одно ключевое но: преподаватель мне сказал, что то, работает или нет программа его волнует в последнюю очередь. Он анализирует код и задаёт мне постоянно один и тот же вопрос: "какой смысл сравнивать с незаданным b[j]?". Я задавал b[j], равный 0, программа тоже работала, но тогда он мне задал вопрос: "ты сравниваешь все числа с b[j], равным нулю. Какой в этос смысл?". Вот код написанной мною программы:

Код
//Даны натуральное n, целые числа a1, ..., an. Внутри данной последовательности могут быть поваторяющиеся члены. 
//Выяснить, сколько чисел входит в последовательность по одному разу
#include <stdio.h>
const int N=100;
void inMas1(int &n, int a[N])
{
        //ввод размерности массива
        printf ("Vvedite razmernost pervogo massiva n=");
        scanf ("%d", &n);
        //проверка на корректность введённой размерности массива
        if (n<=0)
        {
                printf ("Nekorrektniy vvod \n");
        }
        for (int i=0; i<n; i++)
        {
                //ввод a[i]
                printf ("a[%d]=", i);
                scanf ("%d", &a[i]);
        }
}
void MasNoPovtor(int n, int a[], int &k, int b[])
{
        //начальное присвоение
        k=0;
        //Просмотр массива a[N] с занесением всех неповторяющихся элементов этого массива в b[N]
        for (int i=0; i<n; i++)
        {
                //начальное присвоение
                bool flagNo=true;
                int j=0;
                while ((flagNo)&&(j<n))
                {
                        //цикл сравнения
                        if (a[i]==b[j])
                        {
                                flagNo=false;
                        }
                        j++;
                }
                if (flagNo)
                {
                        //добавление a[i] в b[k]
                        b[k]=a[i];
                        k++;
                }
        }
}
void main()
{
        //определение переменных
        int n, k, a[N], b[N];
        //ввод исходных данных
        inMas1(n, a);
        //вычисление b
        MasNoPovtor(n, a, k, b);
        //вывод результата
        if (n>0)
        {
        printf ("%d", k);
        printf ("\n");
        }
}
Собсно, нужно обосновать этот момент. Либо же, писать программу по-другому. Буду благодарен за помощь
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.10.2011, 16:54     Выяснить, сколько чисел входит в последовательность по одному разу
Посмотрите здесь:

C++ Дана последовательность чисел. Выяснить , сколько раз в ней встречается максимальное число.
Выяснить, входит ли в последовательность S1 ,. . ., Sm буква Ю C++
Для каждого из чисел массива выяснить, сколько раз каждое из них входит в этот массив C++
C++ Сформировать список L включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входит во второй из них
Дана последовательность чисел. Выяснить , сколько раз в ней встречается максимальное число. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
29.10.2011, 18:30     Выяснить, сколько чисел входит в последовательность по одному разу #2
Glam_Man, суть в том, что ваш массив b[N], статический и сравнивать значения с ним действительно нет смысла, потому что все его элементы - мусор. Надо создать вспомогательный динамический массив (можно и без этого конечно, ведь задача сводится к тому чтобы вывести количество неповторяющихся), добаить в него первый элемент массива a (т.е. a[0]), и дальше в случае необходимости расширять с помощью realloc. Но повторюсь что для выполнения задачи вспомогательный массив не нужен в принципе. Могу переписать покомпактней.

Добавлено через 1 час 25 минут
вот смотрите. я сначала писал на одном массиве, а потом решил добавить вспомогательный массив, просто так . На самом деле он не нужен вовсе.
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int double_num(int *arr, const size_t N){
 
    int tmp = 0, flag, *arr_tmp;
 
    arr_tmp = (int*) malloc (sizeof(int));
    if ( !arr_tmp )
        exit ( -1 );
 
    for (int i = 0; i < N; ++i)
    {
        flag = 1;
 
        for (int k = 0; k < N; ++k)
            if( ( arr[ i ] == arr[ k ] ) & ( i != k ) )
            {
                flag = 0;
                break;
            }
 
        if ( flag )
        {
            ++tmp;
 
            arr_tmp = realloc(arr_tmp, tmp * sizeof(int));
            if ( !arr_tmp )
                exit ( -1 );
 
            arr_tmp[ tmp - 1 ] = arr[ i ];
        }
    }
 
    for (int i = 0; i < tmp; ++i)
        printf("%d ", arr_tmp[i]);
    printf("\n");
 
    free(arr_tmp);
    return tmp;
}
 
int main ()
{
    int *arr;
    const size_t N = 20;
    srand(time(0));
 
    arr = (int*)malloc(N * sizeof(int));
    if ( !arr )
        exit ( -1 );
 
    for (int i = 0; i < N; ++i)
    {
        arr[i] = rand() % N;
        printf("%d ", arr[i]);
    }
    printf("\n");
    printf("неповторяющихся элементов %i\n\n", double_num(arr, N));
 
    free(arr);
    return 0;
}
Glam_Man
6 / 6 / 0
Регистрация: 15.10.2011
Сообщений: 73
30.10.2011, 06:45  [ТС]     Выяснить, сколько чисел входит в последовательность по одному разу #3
alkagolik
Спасибо за старания, но вы используете много того, чего нам пока что запрещают использовать. То, что можно обойтись одним массивом я уже понял. Не могли бы вы мне ещё пояснить, почему же моя программа всё правильно считает?
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
30.10.2011, 06:54     Выяснить, сколько чисел входит в последовательность по одному разу #4
Цитата Сообщение от Glam_Man Посмотреть сообщение
вы используете много того, чего нам пока что запрещают использовать

Не по теме:

Запрещённые функции си, скандалы, интриги, расследования


На самом деле преподаватель прав. Но ваш алгоритм можно (и нужно изменить) так:
у нас в k лежит количество элементов в массиве b, поэтому и сравнения надо делать в цикле не до n, а до k
C++
1
2
                while ((flagNo)&&(j<k))
                {
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
30.10.2011, 09:44     Выяснить, сколько чисел входит в последовательность по одному разу #5
Цитата Сообщение от mimicria Посмотреть сообщение
у нас в k лежит количество элементов в массиве b, поэтому и сравнения надо делать в цикле не до n, а до k
не выйдет. этот прием гарантирует что мы получим каждое из всех чисел (и те, которые повторяются) только один раз, т.е. перепечатаем все числа, включая повторяющиеся, но без повторов. Надо именно 2 полных прохода по одному циклу (можно с обрывами цикла) чтобы проверить повторное вхождение.
Цитата Сообщение от Glam_Man Посмотреть сообщение
Не могли бы вы мне ещё пояснить, почему же моя программа всё правильно считает?
ну собственно сказал. Сравнивать надо массив с самим собой. Считать вхождения каждого числа (это если тупо). Второй массив сбивает с толку, потому что он не нужен. Правильно вам преподаватель говорит, какой в этом смысл (если это ничего не меняет)? строки 13 - 21 и есть алгоритм поиска.
вот оно же, но с одним статическим массивом. Ничего лишнего, и все просто.
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
#include <stdio.h>
#include <time.h>
 
int double_num(int *arr, const size_t N){
 
    int tmp = 0, flag;
 
    for (int i = 0; i < N; ++i)
    {
        flag = 1;
 
        for (int k = 0; k < N; ++k)
            if( ( arr[ i ] == arr[ k ] ) & ( i != k ) )
            {
                flag = 0;
                break;
            }
 
        if ( flag )
            ++tmp;
    }
    return tmp;
}
 
int main ()
{
    const size_t N = 20;
    int arr[N];
    srand(time(0));
 
    for (int i = 0; i < N; ++i)
    {
        arr[i] = rand() % N;
        printf("%d ", arr[i]);
    }
    printf("\n");
    printf("неповторяющихся элементов %i\n\n", double_num(arr, N));
 
    return 0;
}
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
30.10.2011, 09:58     Выяснить, сколько чисел входит в последовательность по одному разу #6
Цитата Сообщение от alkagolik Посмотреть сообщение
не выйдет. этот прием гарантирует что мы получим каждое из всех чисел (и те, которые повторяются) только один раз, т.е. перепечатаем все числа, включая повторяющиеся, но без повторов. Надо именно 2 полных прохода по одному циклу (можно с обрывами цикла) чтобы проверить повторное вхождение.
Я понял, думал надо просто отбросить повторы Тогда да, сравнивать надо один и тот же массив
Цитата Сообщение от alkagolik Посмотреть сообщение
if( ( arr[ i ] == arr[ k ] ) & ( i != k ) )
&&
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
30.10.2011, 10:57     Выяснить, сколько чисел входит в последовательность по одному разу #7
Цитата Сообщение от mimicria Посмотреть сообщение
&&
разница? логическое И с множеством {0,1} почему не битовая? ( arr[ i ] == arr[ k ] ) вернет {0, 1} и ( i != k ) вернет {0, 1} так зачем же усложнять.

Добавлено через 12 минут
я точно не знаю, но если подумать логически, то на уровне микросхемы функция x && y возвращает z = фи(x) & фи(y), где фи(альфа) = альфа | альфа с выходом в младший бит (мультиплексирование), в то время как побитовая ограничится только одной векторной бинарной операцией z = x & y. Тоже касается и остальных функций. Попроавьте кто-то если не так.
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
30.10.2011, 11:01     Выяснить, сколько чисел входит в последовательность по одному разу #8
Цитата Сообщение от alkagolik Посмотреть сообщение
разница?
Насколько я понимаю, разница в том, что при && второе условие даже не будет рассчитываться, если первое уже ложно
Glam_Man
6 / 6 / 0
Регистрация: 15.10.2011
Сообщений: 73
31.10.2011, 09:01  [ТС]     Выяснить, сколько чисел входит в последовательность по одному разу #9
alkagolik
Нам пока что запрещают использовать условный выход break. rand() и запись вида "++<идентификатор счётчика>" также запрещены
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.10.2011, 09:24     Выяснить, сколько чисел входит в последовательность по одному разу #10
Цитата Сообщение от Glam_Man Посмотреть сообщение
Нам пока что запрещают использовать условный выход break. rand() и запись вида "++<идентификатор счётчика>" также запрещены
если вы уберете break, то алгоритм не тработает. надо в этом случае полностью менять подход к решению задачи. Вы точно уверены в том что это имнно ЗАПРЕЩЕНО? Если нет, то можно проявить инициативу (уверен в том, что она будет принята начальником).
Вместо rand() используйте ввод с клавиатуры (не буду же я за вас сидеть и долбить по клаве, верно?)
Непонятно почему запрещено использовать инкремент, но если уж так, то вместо инкремента можете вписать строки типа x = x + 1;

Добавлено через 8 минут
Цитата Сообщение от mimicria Посмотреть сообщение
Насколько я понимаю, разница в том, что при && второе условие даже не будет рассчитываться, если первое уже ложно
сигнал о том - вычислять дальше или нет, тоже должен поступить в результате вычислений... и в данном примере как для битовой операции, так и для "псевдологической" используется одна КС, так что при машинном нуле в первом условии в обоих случаях второе условие не вычисляется, я потому и подчеркнул что имеем дело с множеством {0, 1}, и следовательно лучше использовать именно битовую функцию. в рамках данной задачи разницы нет, но когда речь идет об экономии ресурсов - такая мелочь вполне может "отсеять" миллионы лишних операций.
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
31.10.2011, 09:32     Выяснить, сколько чисел входит в последовательность по одному разу #11
Цитата Сообщение от alkagolik Посмотреть сообщение
так что при машинном нуле в первом условии в обоих случаях второе условие не вычисляется
Вычисляется, в этом то и вся разница
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.10.2011, 09:37     Выяснить, сколько чисел входит в последовательность по одному разу #12
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdlib.h>
....
int double_num(int *arr, const size_t N){
 
    int tmp = 0, flag;
 
    for (int i = 0; i < N; ++i)
    {
        flag = 0;
 
        for (int k = 0; k < N; ++k)
            if( ( arr[ i ] == arr[ k ] ) & ( i != k ) )
                flag = flag + 1;
 
        if ( flag == 1 )
            tmp = tmp + 1;
    }
    return tmp;
}
Добавлено через 3 минуты
Цитата Сообщение от mimicria Посмотреть сообщение
Вычисляется, в этом то и вся разница
друг, не убедил. давай по существу. Что вычисляется, как вычисляется, почему именно так...
Glam_Man
6 / 6 / 0
Регистрация: 15.10.2011
Сообщений: 73
31.10.2011, 09:38  [ТС]     Выяснить, сколько чисел входит в последовательность по одному разу #13
Если заменить "++i" на "i++" в 7 строке, то ничего не изменится?
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
31.10.2011, 09:38     Выяснить, сколько чисел входит в последовательность по одному разу #14
Цитата Сообщение от alkagolik Посмотреть сообщение
друг, не убедил. давай по существу. Что вычисляется, как вычисляется, почему именно так...
Простейший тест убедит?
C++
1
2
3
4
5
6
 int test=5, d;
 if(false && test++>10) d=100; // это называется неполное вычисление булевых выражений
 cout << test << endl;
 test=5;
 if(false & test++>10) d=100;
 cout << test << endl;
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.10.2011, 10:05     Выяснить, сколько чисел входит в последовательность по одному разу #15
Цитата Сообщение от Glam_Man Посмотреть сообщение
Если заменить "++i" на "i++" в 7 строке, то ничего не изменится?
нет, не изменится. смотри, "++i" - это ПРЕфиксная запись. В этом случае она имеет наивысший приоритет. т.е. в случае при x = 4; y = ++x; сначала вычисляется x = x + 1, а уже после y = x. в случае же ПОСТфиксиной записи "x++", будет сначала вычислено y = x, а уже после x = x + 1;
Цитата Сообщение от mimicria Посмотреть сообщение
Простейший тест убедит?
нет, не убедил. мнепоказалось что вы не имеете представления о предмете разговора. Вы рассуждаете в аспекте высокоуровневого программирования, в то время как я говорю вам о работе транзисторов. То что человеческий мозг вычисляет и при этом человек не замечает, не распростроняется на технику. Приемнику нужен точный сигнал - вычислять данную КС или ее не вычислять. В рамках данной дискуссии говорю (повторяюсь) что для этой задачи существует одна КС, которая отрабатывается обоими функциями (псевдологическая(последующая из бинарной) "&&" и баниарная "&").
Кроме того вы пытаетесь ввести меня(или себя) в заблуждение лексемами "if false &" "if false &&", что любыми компилятороми преобразуется в нуль.
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
31.10.2011, 10:11     Выяснить, сколько чисел входит в последовательность по одному разу #16
Цитата Сообщение от alkagolik Посмотреть сообщение
Кроме того вы пытаетесь ввести меня(или себя) в заблуждение лексемами "if false &" "if false &&", что любыми компилятороми преобразуется в нуль.
Я Вам еще раз повторю. Если мы используем логическое И, то второе выражение НЕ вычисляется, если результат вычисление первого ложь. В случае оператора & вычисление будет в любом случае производиться. Тест это доказывает. Я и пишу false для проверки. Можете написать там любое другое выражение, которое будет ложным.
И не надо лечить про транзисторы.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.10.2011, 10:57     Выяснить, сколько чисел входит в последовательность по одному разу #17
Цитата Сообщение от mimicria Посмотреть сообщение
Если мы используем логическое И
а что такое логиечкое И, и как оно реализовано техникой? В то время как операнды представлены 8 битами. Сигнал о дальнейшем продолжении операции тоже вычисляется...

Добавлено через 17 минут
эот код демонстрирует логику работы процессора.
C
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
int main ()
{
    printf("%i\n", 2 && 4);
    printf("%i\n", 2 & 4);
    printf("%i\n", 4 && 4);
    printf("%i\n", 4 & 4);
 
    return 0;
}
из него видно, что в случае функции && сначала мультиплексируются операнды, а после производится векторная функция между ними, в то время как в функции "&" только производится бинарная операция "логическое И". Из чего следует вывод что функция "&&" требует дополнительных вычислений, которые заключаются в мультиплексировании операндов в младший бит и обнулении всех остальных битов. Следовательно при точном определении множеств (т.е. мы точно знаем что оперируем двоичным множеством) {0, 1} не стоит усугублять процесс дополнительными ресурсами ("&&").
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
31.10.2011, 11:08     Выяснить, сколько чисел входит в последовательность по одному разу #18
Цитата Сообщение от alkagolik Посмотреть сообщение
а что такое логиечкое И, и как оно реализовано техникой?
Я не понимаю, что Вы хотите этим сказать или доказать. Сколько раз нужно повторить, что разница между ними есть? Вот разница в ассемблере, если вы переживаете за оптимизацию компилятором.
Исходник, отличается в 1 и 2 случае только количеством амперсандов:
C++
1
2
 int test=5,d=10;
 if(d>50 && test++>10) d=100;
Вариант &:
Выяснить, сколько чисел входит в последовательность по одному разу
Явно виден всего один условный переход после вычисления ОБОИХ условий. Т.е. независимо от того, что первое условие ложно, второе всё равно вычисляется


Вариант &&:
Выяснить, сколько чисел входит в последовательность по одному разу
Первый переход на выход СРАЗУ после вычисления первого условия. БЕЗ вычисления второго.
Вобщем-то я больше не буду ничего доказывать, если Вам этого недостаточно.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
31.10.2011, 11:46     Выяснить, сколько чисел входит в последовательность по одному разу #19
Цитата Сообщение от mimicria Посмотреть сообщение
Т.е. независимо от того, что первое условие ложно, второе всё равно вычисляется
глупость. никакие "условия" в битовых операциях не вычисляются. "условия" вычисляются в "псевдологическоих" операциях, и то только потому что сами "условия" тоже надо вычислить. Пример:
"Псевдологическая операция (логическое И)":
имеем 2 операнда: x, y;
пусть х = 0;
для того чтобы машина знала что х = 0, ей надо произвести ряд определенных инженером (программистом) действий, а именнно - совершить мультиплексироание логического ИЛИ каждодго бита с самим собой, и на выходе получить результат. Этот результат пройдет по отдельному каналу (опять же определенному инженером), и в случае низкого тока откроет выдачу машинного нуля.

Пусть х = 1.
Для того чтобы машина знала что х > 0 или x < 0 - ей надо произвести ряд определенных инженером (программистом) действий, а именнно - совершить мультиплексироание логического ИЛИ каждодго бита с самим собой, и на выходе получить результат. Результат записать в младший бит операнда и при этом обнулить все остальные биты.

Сколько операций??? а если первое условие все таки - истина, сколько тогда операций?

бинарная векторная функция "&".

не зависит от операндов (0 & 1; 5 & 6; 8 & 4). Что это значит? Это значит то, что мы избавлены от дополнительных вычислений (при "псевдологических" операциях именно эти вычисления и совершаются) - мультиплексирования положительного бита в младший, и обнуления остальных. Просто два регистра пропускают свои биты через КС, которая выходит в шину данных.
З.Ы не пугайте меня ассемблерами... Я говорю вам лишь о том что условия переходов тоже вычисляются... этого вам ни один дизасм(тем более DOS) не покажет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2011, 12:22     Выяснить, сколько чисел входит в последовательность по одному разу
Еще ссылки по теме:

Дана последовательность чисел. Выяснить, сколько раз в ней встречается максимальное число C++
Даны натуральное n и целые a1, a2, ., an. Найти сколько чисел входят в последовательность более чем по 1 разу C++
Символьный тип данных, выяснить входит ли в последовательность s1, s2, …, sn буква j C++

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

Или воспользуйтесь поиском по форуму:
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
31.10.2011, 12:22     Выяснить, сколько чисел входит в последовательность по одному разу #20
Цитата Сообщение от alkagolik Посмотреть сообщение
никакие "условия" в битовых операциях не вычисляются
У нас есть составное условие if ((первое_условие)&&(второе_условие))
В случае & оба условия вычисляются. В случае && второе условие вычисляется только если результат вычисления первого = 1.
Цитата Сообщение от alkagolik Посмотреть сообщение
Сколько операций???
Судя по листингу (считаю до выхода)
для &: 15 операций, из них 2 сравнения и 1 условный переход
для &&:
- лучший случай: 7 операций, из них 1 сравнение и 1 условный переход
- худший случай: 11 операций, из них 2 сравнения и 2 условных перехода
Выигрыш налицо. А чем свою психоделическую теорию докажете Вы?

Не по теме:

Предлагаю тогда уж вынести эту тему на отдельное общее обсуждение за рамки данного топика.

Yandex
Объявления
31.10.2011, 12:22     Выяснить, сколько чисел входит в последовательность по одному разу
Ответ Создать тему
Опции темы

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