Найти в матрице единственный элемент противоположного знака по отношению к другим

@Aliksan · Регистрация: 22.09.2015

Author24 — интернет-сервис помощи студентам

Добрый вечер.
Я вас уже стал слишком часто беспокоить, хорошо, однако, кой-какие недостатки исправляю сам.
Есть программа, которая работает: она ищет один единственный элемент в матрице, который противоположного знака, чем все остальные. Это значит, что если в матрице NxM все элементы положительные, и один единственный отрицательный (нулей нет, они исключены), то ответ будет: Отрицательный. И наоборот.
Но это работает, когда вводимые N и M соответственно небольшие.
Когда я ввожу 100000000000000000 и 100000000000000000 (или даже чуть меньшее число), то пишет:

C

1	Segmentation fault (core dumped)

Однако, я выделил память под Long Long.

Где ошибка?

Вот код:

C

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    long long i, j, eilute, stulpelis, elementas;
    int skaitliukas_teigiamu = 0;
    int skaitliukas_neigiamu = 0;
    
    scanf ("%lld %lld", &eilute, &stulpelis);
 
        long long **array = (long long **) malloc(eilute * sizeof(long long *));
        for(i = 0; i < eilute; i++) {
            array[i] = (long long *) malloc(stulpelis * sizeof(long long));
        }
 
    for(i = 0; i < eilute; i++) {
        for(j = 0; j < stulpelis; j++) {
            scanf("%lld", &elementas);
                if (elementas > 0) {
                    skaitliukas_teigiamu++;
                }
                if (elementas < 0) {
                    skaitliukas_neigiamu++;
                }
        }
    }
 
    if (skaitliukas_teigiamu > skaitliukas_neigiamu) {
        printf("Neigiamas\n");
    }
 
    if (skaitliukas_neigiamu > skaitliukas_teigiamu) {
        printf("Teigiamas\n");
    }
// free(array);
return 0;
}

@Rius · 09.05.2016, 08:49

Это размеры двухмерного массива?
В настоящее время на этой планете нет компьютеров с таким объёмом памяти.
А чтобы ввести все элементы вручную, Вам не хватит времени до конца Вселенной.

@Aliksan · 09.05.2016, 11:43 **[ТС]**

Попытаюсь еще раз написать требования к программе.
Условие: в заданном прямоугольном массиве все элементы или только положительные, или только отрицательные, кроме одного элемента, у которого противоположный знак чем у других элементов. Написать программу, которая установила бы этот знак. Вывод программы: Положительный или Отрицательный.

Условие: размер массива N, M и Aij. (1 < N, M < 10 в степени 18; -10 в степени 6 < Aij < 10 в степени 6).

Так как? )) Или это у нас препод немного космический? ))

@Rius · 09.05.2016, 11:47

Если надо именно реализовать с такими границами, то скорее всего это опечатка.
Алгоритм не изменится всё равно.
Можно сделать виртуальный массив, но врядли задание это предусматривает, и длительность поиска также будет нереальная.

@Catstail · 09.05.2016, 11:51

В условии задачи явная ошибка. Кстати, long long здесь не нужен, нужен float (если числа от 10^-6 до 10⁶

@Aliksan · 09.05.2016, 12:17 **[ТС]**

Спасибо за советы, а почему float а не int? Целые числа берем ведь....

@Rius · 09.05.2016, 12:28

Aliksan, там ни слова про целые числа в Aij.

@Aliksan · 09.05.2016, 14:30 **[ТС]**

Я не добавил, что числа целые, да, все понятно. Спасибо!

Добавлено через 15 минут
Запустил программу в системе контестер. И на последнем тесте выдает ошибку: Time limit.
То бишь программа работает почти аккуратно, но где здесь подвох? Сравнение числа происходит в том же цикле, что и считывание с клавиатуры. Что бы это могло быть?

C

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int i, j, eilute, stulpelis, elementas;
    int skaitliukas_teigiamu = 0;
    int skaitliukas_neigiamu = 0;
    
    scanf ("%d %d", &eilute, &stulpelis);
 
        int **array = (int **) malloc(eilute * sizeof(int *));
        for(i = 0; i < eilute; i++) {
            array[i] = (int *) malloc(stulpelis * sizeof(int));
        }
 
    for(i = 0; i < eilute; i++) {
        for(j = 0; j < stulpelis; j++) {
            scanf("%d", &elementas);
                if (elementas > 0) {
                    skaitliukas_teigiamu++;
                }
                if (elementas < 0) {
                    skaitliukas_neigiamu++;
                }
        }
    }
 
    if (skaitliukas_teigiamu > skaitliukas_neigiamu) {
        printf("Neigiamas\n");
    }
 
    if (skaitliukas_neigiamu > skaitliukas_teigiamu) {
        printf("Teigiamas\n");
    }
free(array);
return 0;
}

Добавлено через 1 час 18 минут
Пришел ответ преподавателя.
В 7 тесте дана таблица 1000х1000, однако, прошу обратить ваше внимание, что программе уделено всего 0,075 секунд, поэтому самый простой код здесь не уместится во временные рамки. Необходимо придумать оптимально работающий код. Вот как...

Добавлено через 7 минут
Тут надо поднять новую тему...

@Rius · 09.05.2016, 14:55

Можно представить двумерный массив как одномерный.
a[row][column] == a[row * column_width + column].
Т.е. для перебора всех элементов достаточно увеличивать указатель на размер 1 элемента.
Хотя с динамическими массивами с отдельным созданием подмассивов это не прокатит.

@Aliksan · 09.05.2016, 15:33 **[ТС]**

Сообщение от Rius

a[row][column] == a[row * column_width + column].

Я это уже где-то видел! Вы не могли бы встроить его вот в этот цикл?...

C

        int **array = (int **) malloc(eilute * sizeof(int *));
        for(i = 0; i < eilute; i++) {
            array[i] = (int *) malloc(stulpelis * sizeof(int));
        }

@Rius · 09.05.2016, 16:35

В этот - нет.
Создайте массив не в 1 + N проходов, а за 1 раз. Сразу размером M * N, одномерный.

@Aliksan · 09.05.2016, 17:42 **[ТС]**

Сообщение от Rius

Сразу размером M * N, одномерный

Переделал программу, но теперь во время запуска кидает вот это:

C

1	Segmentation fault (core dumped)

Сам код програмы.

C

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int i, j, eilute, stulpelis, elementas;
    int *ptr;
    int skaitliukas_teigiamu = 0;
    int skaitliukas_neigiamu = 0;
    
    scanf ("%d %d", &eilute, &stulpelis);
 
//      int **array = (int **) malloc(eilute * sizeof(int *));
//      for(i = 0; i < eilute; i++) {
//          array[i] = (int *) malloc(stulpelis * sizeof(int));
//      }
 
    if ((*ptr = (int*) malloc(eilute*stulpelis *sizeof(int)) == NULL)) {
        return 0;
    } else {
        for(i = 0; i < eilute*stulpelis; i++) {
            *(ptr + i) = i;
        }
            for(i = 0; i < eilute; i++) {
                for(j = 0; j < stulpelis; j++) {
                scanf("%d", &elementas);
                    if (elementas > 0) {
                        skaitliukas_teigiamu++;
                    }
                    if (elementas < 0) {
                        skaitliukas_neigiamu++;
                    }
                }
            }
    }
 
 
    if (skaitliukas_teigiamu > skaitliukas_neigiamu) {
        printf("Neigiamas\n");
    }
 
    if (skaitliukas_neigiamu > skaitliukas_teigiamu) {
        printf("Teigiamas\n");
    }
//free(array);
return 0;
}

Всех поздравляю с праздником!

@Rius · 09.05.2016, 17:51

C++

1	if ((ptr = (int)malloc(eilutestulpelis *sizeof(int))) == NULL) {

Скобки не там и звездочка лишняя.
Пользуйтесь пошаговым отладчиком.

@Aliksan · 09.05.2016, 19:10 **[ТС]**

Сообщение от Rius

Скобки не там и звездочка лишняя.
Пользуйтесь пошаговым отладчиком.

Заработало!!! Урра!

Пишу код, может кому пригодится!

C

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int i, j, eilute, stulpelis, elementas;
    int *ptr;
    int skaitliukas_teigiamu = 0;
    int skaitliukas_neigiamu = 0;
    
    scanf ("%d %d", &eilute, &stulpelis);
 
    if ((ptr = (int*) malloc(eilute*stulpelis *sizeof(int))) == NULL) {
        return 0;
    } else {
        for(i = 0; i < eilute*stulpelis; i++) {
            *(ptr + i) = i;
        }
            for(i = 0; i < eilute; i++) {
                for(j = 0; j < stulpelis; j++) {
                scanf("%d", &elementas);
                    if (elementas > 0) {
                        skaitliukas_teigiamu++;
                    }
                    if (elementas < 0) {
                        skaitliukas_neigiamu++;
                    }
                }
            }
    }
 
    if (skaitliukas_teigiamu > skaitliukas_neigiamu) {
        printf("Otricatelnoe\n");
    }
 
    if (skaitliukas_neigiamu > skaitliukas_teigiamu) {
        printf("Polozitelnoe\n");
    }
//free(array);
return 0;
}

@Catstail · 09.05.2016, 19:40

Если условие задачи формулируется так: все элементы, кроме одного имеют один и тот же знак, и ровно один имеет противоположный знак, и нужно найти этот противоположный знак (напечатать "положительный" или "отрицательный"), то просматривать весь массив не нужно. Достаточно взять три любых элемента - и все! Возможные случаи:
- все три > 0 -> ответ отрицательный
- все три < 0 -> ответ положительный
- два > 0, один меньше - ответ отрицательный
- два < 0, один больше - ответ положительный

Работать это будет очень быстро.

@Aliksan · 09.05.2016, 19:58 **[ТС]**

Сообщение от Catstail

Работать это будет очень быстро.

Я думал об этом, но мысль куда-то затерялась... Так получается, что моя программа может посчитать все положительные и все отрицательные значения. )
Спасибо, за замечание, админ!

@Catstail · 09.05.2016, 20:01

Сообщение от Aliksan

Так получается, что моя программа может посчитать все положительные и все отрицательные значения

- да, но по условию этого не нужно.

@Rius · 09.05.2016, 20:04

Точно, оказывается координаты самого элемента не нужны по заданию

Поэтому числа такие большие, чтобы намекать на ненужность полного просмотра.

@Rius 10571 / 6495 / 1506 Регистрация: 25.05.2015 Сообщений: 19,671 Записей в блоге: 14
	09.05.2016, 08:49	2
	Это размеры двухмерного массива? В настоящее время на этой планете нет компьютеров с таким объёмом памяти. А чтобы ввести все элементы вручную, Вам не хватит времени до конца Вселенной. 0

@Aliksan 7 / 7 / 3 Регистрация: 22.09.2015 Сообщений: 173
	09.05.2016, 11:43 [ТС]	3
	Попытаюсь еще раз написать требования к программе. Условие: в заданном прямоугольном массиве все элементы или только положительные, или только отрицательные, кроме одного элемента, у которого противоположный знак чем у других элементов. Написать программу, которая установила бы этот знак. Вывод программы: Положительный или Отрицательный. Условие: размер массива N, M и Aij. (1 < N, M < 10 в степени 18; -10 в степени 6 < Aij < 10 в степени 6). Так как? )) Или это у нас препод немного космический? )) 0

@Rius 10571 / 6495 / 1506 Регистрация: 25.05.2015 Сообщений: 19,671 Записей в блоге: 14
	09.05.2016, 11:47	4
	Если надо именно реализовать с такими границами, то скорее всего это опечатка. Алгоритм не изменится всё равно. Можно сделать виртуальный массив, но врядли задание это предусматривает, и длительность поиска также будет нереальная. 0

@Catstail Модератор 36606 / 20334 / 4221 Регистрация: 12.02.2012 Сообщений: 33,653 Записей в блоге: 13
	09.05.2016, 11:51	5
	В условии задачи явная ошибка. Кстати, long long здесь не нужен, нужен float (если числа от 10^-6 до 10⁶ 0

@Aliksan 7 / 7 / 3 Регистрация: 22.09.2015 Сообщений: 173
	09.05.2016, 12:17 [ТС]	6
	Спасибо за советы, а почему float а не int? Целые числа берем ведь.... 0

@Rius 10571 / 6495 / 1506 Регистрация: 25.05.2015 Сообщений: 19,671 Записей в блоге: 14
	09.05.2016, 12:28	7
	Aliksan, там ни слова про целые числа в Aij. 0

@Rius 10571 / 6495 / 1506 Регистрация: 25.05.2015 Сообщений: 19,671 Записей в блоге: 14
	09.05.2016, 14:55	9
	Можно представить двумерный массив как одномерный. a[row][column] == a[row * column_width + column]. Т.е. для перебора всех элементов достаточно увеличивать указатель на размер 1 элемента. Хотя с динамическими массивами с отдельным созданием подмассивов это не прокатит. 1

@Rius 10571 / 6495 / 1506 Регистрация: 25.05.2015 Сообщений: 19,671 Записей в блоге: 14
	09.05.2016, 16:35	11
	В этот - нет. Создайте массив не в 1 + N проходов, а за 1 раз. Сразу размером M * N, одномерный. 1

@Catstail Модератор 36606 / 20334 / 4221 Регистрация: 12.02.2012 Сообщений: 33,653 Записей в блоге: 13
	09.05.2016, 19:40	15
	Сообщение было отмечено Rius как решение Решение Если условие задачи формулируется так: все элементы, кроме одного имеют один и тот же знак, и ровно один имеет противоположный знак, и нужно найти этот противоположный знак (напечатать "положительный" или "отрицательный"), то просматривать весь массив не нужно. Достаточно взять три любых элемента - и все! Возможные случаи: - все три > 0 -> ответ отрицательный - все три < 0 -> ответ положительный - два > 0, один меньше - ответ отрицательный - два < 0, один больше - ответ положительный Работать это будет очень быстро. 2

@Aliksan 7 / 7 / 3 Регистрация: 22.09.2015 Сообщений: 173
	09.05.2016, 19:58 [ТС]	16
	Сообщение от Catstail Работать это будет очень быстро. Я думал об этом, но мысль куда-то затерялась... Так получается, что моя программа может посчитать все положительные и все отрицательные значения. ) Спасибо, за замечание, админ! 0

@Catstail Модератор 36606 / 20334 / 4221 Регистрация: 12.02.2012 Сообщений: 33,653 Записей в блоге: 13
	09.05.2016, 20:01	17
	Сообщение от Aliksan Так получается, что моя программа может посчитать все положительные и все отрицательные значения - да, но по условию этого не нужно. 0

@Rius 10571 / 6495 / 1506 Регистрация: 25.05.2015 Сообщений: 19,671 Записей в блоге: 14
	09.05.2016, 20:04	18
	Точно, оказывается координаты самого элемента не нужны по заданию Поэтому числа такие большие, чтобы намекать на ненужность полного просмотра. 0

Найти в матрице единственный элемент противоположного знака по отношению к другим

Решение