Что нужно подтянуть?

Question

Что нужно подтянуть?

Рейтинг: 0Ответов: 2Опубликовано: 20.06.2011

За два курса в университете понял, что я ни черта не умею программировать. Сейчас хочу решить эту проблему. Для начала, думаю, нужно выяснить, что мне нужно повторить. Алгоритмическое мышление хромает и знания языка хромают. Вот выкладываю задачку, которую пытался решить. Найти количество различных элементов в массиве. Задачки решена не правильно, но пока я не могу понять, как решить. С помощью этой задачи хочу выявить свои пробелы и получить рекомендации, как их устранить. Заранее благодарен.

#include <iostream>

using namespace std;

int main()
{
    const int size = 10;

    int arr[size] = { 10, 1, 1, 3, 1, 3, 1, 8, 9, 2 };
    int count = 0;

    for (int i = 0; i < size; ++i)
    {
        for (int j = size - 1; j > i; --j)
        {
            if (arr[i] != arr[j])
            {
                count++;

                break;
            }
            else
                --j;
        }
    }

    cout << count << endl;

    return 0;
}

c#

Источник: Stack Overflow на русском

Answer 1

▲ 3

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

Такие задачи решаются большим количеством способов, например, сортировкой элементов, с последующим пробегом по массиву и подсчетом кол-ва раз когда a[i-1] != a[i], или эмуляцией множества реализованного на массиве (пусть а[] - массив , представляющий множество, пробегаем по входному массиву чисел c[] и делаем a[c[i]]=true, затем считаем сколько элементов в массиве a[] имеют значение true), а дальше деревья и т.д.

P.S. У способа с множеством есть недостаток память будет расходоваться зря, поэтому это не самый лучший выбор, по мне так сортировка самое оно, а для сортировки можно использовать QuickSort (для тренировки мышления), хотя конечно выбор сортировки зависит от многих показателей, в том числе и лени :)

P.S.S. Еще мой извращенный ум подсказывает, что множество можно реализовать на битовом массиве :) получится весьма компактно)

Answer 2

▲ 3

Уважаемый @ArniLand !

Не обижайтесь, но боюсь, что рассуждения в замечательном ответе @GLAGOLA пока мало что дадут Вам в плане решения задачи. Ознакомьтесь с примитивным решением.

#include <stdio.h>
#include <stdlib.h>

/*
  Подсчет количества разных.
 */
int ndiff (int *arr, int size)
{
  if (size <= 0)
      return 0;

  int
    /*
      set - 'как бы множество' т.е. сюда поместим элемент arr[], если такого еще нет.
      В конце работы количество элементов set[] это решение задачи.
    */
    *set = malloc(sizeof(int)*size), 
    i, j, 
    n;  // Это сколько уже поместили в set[]

  set[0] = arr[0];  // Хотя бы один должен быть даже если все одинаковые
  n = 1;

  for (i = 1; i < size; i++) { //  Для каждого элемента массива 
    for (j = 0; j < n; j++) {  //  просматриваем уже накопленное 'множество'
      if (set[j] == arr[i])    //  такой уже встречался ?
          break;
    }
    if (j == n)                // такого arr[i] еще не было
      set[n++] = arr[i];       // добавим его в 'множество'
  }

  free(set);
  return n;
}

main ()
{
  static int arr[] = {10, 1, 1, 3, 1, 3, 1, 8, 9, 2 };
  int        size = sizeof(arr)/sizeof(int);

  printf ("ndiff = %d\n",ndiff(arr,size));
  exit(0);
}

Эта программа ужасно неэффективна по памяти и времени исполнения, зато крайне проста.

Что нужно подтянуть?

Ответы