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

задачи на основные темы, требующие как минимум присутствие логики - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Структура http://www.cyberforum.ru/cpp-beginners/thread208286.html
Написать структуру 4 4 Ivanov 51 2 Zuckerberg 99.1 3 Mendelson 99.0 1 Ivanova 55.1 i 2 1 Ivanova 55.1 4 Ivanov 51
C++ В квадратный числовой массив записаны целые числа в диапазоне от -99 до 99. Определить, имеются ли такие квадратные подмассивы, сумма элементов которы В квадратный числовой массив записаны целые числа в диапазоне от -99 до 99. Определить, имеются ли такие квадратные подмассивы, сумма элементов которых равна P. Если таковые имеются, то вывести эти подмассивы на экран. http://www.cyberforum.ru/cpp-beginners/thread208277.html
Функция+binary + АНГЛ!!! C++
3 задачи! Официальным языком форума является русский язык. Будьте так добры, потрудитесь и переведите тексты заданий
Заполнение массива по спирали C++
Дано число n. Создайте массив A и заполните его по спирали, начиная с числа 0 в центральной клетке A. Спираль выходит вверх, далее закручивается против часовой стрелки. очень нужно помагите
C++ Массив структур http://www.cyberforum.ru/cpp-beginners/thread208267.html
Задача:создать массив структур а,содержащий фамилию и 3 оценки.Найти студентов,чей средний балл выше среднего группы и упорядочить по алфавиту. Получить массив и вывести на экран. вышел такой код: #include <iostream> #include <string.h> #include <iomanip> #include <conio.h> using namespace std;
C++ Полное решение, классы!!! + проверь свой АНГЛ!!! необходимо полное решение с оформлением подробнее

Показать сообщение отдельно
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
13.12.2010, 00:10     задачи на основные темы, требующие как минимум присутствие логики
Хорошие задачки. Давно такого здесь не было.
Начнем пока с конца.
Номер 5.
Если б все точки имели разные Y-координаты - задача тривиальна. Находим точки со средними координатами (если N-четное таких точек 2, нечетное - 1) и проводим прямую между ними, скажем
y = (Ay - By)/ 2 или y = Ay / 2 (Ay, By - Y-координаты этих точек.)
А что делать, ежели наше условие не выполняется?
Составляем вектора между всеми парами точек (их всего N*(N-1)/2 ), считаем тангенсы углов ихнего наклона (Vy/Vx) и находим 2 наименьших (но разных!). Если самый наименьший != 0, то имеем рассмотренный выше тривиальный случай. Иначе вот что.
Берем минимальный не нулевой тангенс (скажем t) и строим прямую с углом наклона t/2
У нее есть такое замечательное свойство, что на всех таких прямых не больше 1-й точки нашего множества.
Берем любую такую прямую, скажем y - (t/2) * x =0
Далее, координаты всех наших точек по очереди подставляем в y-(t/2)*x (это будет расстояние от нашей прямой) и из полученных чисел выбираем среднее (или пару средних) и через эту точку (или между 2-мя в четном случае) проводим искомую прямую.
Остается еще один дурацкий случай - все тангенсы = 0. Но это значит, что все точки лежат на оси X (параллельно ей) и задача сводится к тривиальному случаю с переменой осей.
Если все это не слишком понятно, посмотри внимательно на "тривиальный" случай, картинку нарисуй. Дальше все будет понятно.

Номер 2.
Есть кой-какие соображения, но там уж прямо почти коды надо писать.
Идея - тупой перебор
C
1
2
3
4
5
6
7
8
9
10
for(j=0; j<N; j++) {
  M = 1;  // Кол-во чесел в группе
  // находим множество простых делителей a[i]
  for(i=j+1;j<N;j==) {
     // множество простых делителей a[j]
     // Сравниваем с a[i]
     if (совпадают) M++;
  }
  if (M>Mx) Mx = M; 
}
Там еще куча проблем (вполне решаемых) по поводу представления множеств и сокращения явно излишнего перебора.
Сложность = O(n^3)

Добавлено через 1 час 43 минуты
Задание N 2
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
int a[N]; //- Наши числа
int Mx; // Макксимальное из них
Mx = 1;
for(i=0; i<N; i++) if (a[i] > Mx) Mx = a[i];
char *sk;  // Шкала использования
sk = (char *) malloc(N+1);
sk[N] = '\0';
for(i=0; i<N; i++) sk[i] = 1;  // 1 - не использовано, 2 - использовано
int Mp = sqrt(Mx) / 2;  // Размер массива простых делителей
int *Prim = malloc(2*Mp*sizeof(int)); // список простых чисел
MakePrim()  // Заполнение Prim
{
  Prim[0] = 2;
  n = 1;
  for(i=3; i<2*Mp; i+=2) {
    for(j, 1, n) if (i%Prim) break;
    if (j==n) Prim[n++] = 1;
  }
  return (n);
}
//----------
Delit(int K, int pd)  // Составление списков делителей
{
  for(i=0, j=0; i<Mp; i++) {
    if (K%Prim[i]) continue;
    pd[j++] = Prim[i];
    K /= Prim[i];
    while(K%Prim[i]==0) K /= Prim[i]; // Делим до упора
  }
}
//----------
main()
{
  int NP = MakePrim();
  int *pd1 = (int *) malloc(Mp*sizeof(int));
  int *pd2 = (int *) malloc(Mp*sizeof(int));
  int Vx; // объем подмножества
  int Vmx = 0; // объем максимального подмножества
  int Ix = 0;  // Номер числа - представителя максимальной группы
  for(i=0; i<N; i++) {
    if (sk[i]==2) continue;
    sk[i] = 2;
    Vx = 1;
    int k1 = Delit(a[i], pd1);
    for(j=i+1; j<N; j++) {
      if (sk[j]==2) continue;
      int k2 = Delit(a[j], pd2);
      if (k1==k2) {
        for(ii=0; ii<k1; ii++) if (pd1[ii]!=pd2[ii]) break;
        if (ii==k1) {  // Наше число
           Vx++;
           sk[j] = 2;
        }
      }
    }
    if (Vx > Vmx) {  // Больше всех
      Vmx = Vx;
      Ix = i;
    }
  }
  // Почти все. Vmx - максимальный объем, Ix - представитель множества
  // Повторяя внутренний цикл для i=Ix (не обращая внимания на sk)
  // находим и остальные элементы множества
}
Это, конечно, не рабочий код, а идея (псевдокод)
Надеюсь, дальше ты справишься

Добавлено через 11 минут
Найти в строке тройку слов таких, что из букв двух слов можно получить третье (при составлении этого слова следует использовать все буквы двух других). Если таких троек несколько, вывести ту, которая имеет максимальное суммарное количество букв.
По схеме перебора слегка похоже на N2. Только вместо делителей - буквы. Хотя и есть и свои особенности
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru