0

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

#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;
}
1
  • 5
    @ArniLand Подтянуть надо принятие ответов. А то 0% принятых... 20 июн 2011 в 19:52

4 ответа 4

3

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

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

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

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

2
  • 1
    Небольшой оффтоп, вспомнилась задачка: есть массив целых чисел на входе от 0..MAXINT огромного размера (такой что даже весь в память не влезет, конечно, если его попытаться загрузить) и в этом массиве все числа встречаются четное кол-во раз, а какое-то одно нечетное, нужно пройдя этот массив найти это число. Решалась очень элегантно: нужно было выполнить xor всех элементов входной последовательности, в результате получался ответ. (все основывалось на том, что 5 xor 5 = 0, 5 xor 6 xor 5 = 6)
    – GLAGOLA
    20 июн 2011 в 19:44
  • Если надо сохранить исходный массив нетронутым, то битовое множество лучше, в смысле экономии памяти.
    – avp
    20 июн 2011 в 20:05
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);
}

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

1

Та же программа @avp (copy+paste), но чуть покороче.

#include <iostream>
#include <set>
using namespace std;
main ()
{
  static int arr[] = {10, 1, 1, 3, 1, 3, 1, 8, 9, 2 };
  int        size = sizeof(arr)/sizeof(int);
  set<int> s (arr, arr+size);

  cout << "Количество различных элементов " << s.size() << endl;
  return 0;
}
2
  • Я заплюсовал, но только автору вопроса такой замечательный пример, демонстрирующий стандартные для C++ библиотечные решения, научиться программировать вряд ли поможет.
    – avp
    6 июл 2011 в 11:41
  • Думаю, что наоборот. Представить решение, не вдаваясь в тонкости реализации -- куда полезней. Ну а реализовать те же двоичные деревья (или что там в set) -- этому потом будет легче научиться. И не надо недооценивать фактор трудоёмкости -- написать из любознательности десять строк или сто -- разница есть.
    – alexlz
    6 июл 2011 в 11:46
0

Извините за оффтопик. Если хотите подтянуть знания по C++. Книжки Скотта Мейерса Вам в помощь будет + перечитайте Страуструпа

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.