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

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

Восстановить пароль Регистрация
 
ПолинаФ
2 / 2 / 0
Регистрация: 08.12.2010
Сообщений: 7
11.12.2010, 09:16     задачи на основные темы, требующие как минимум присутствие логики #1
!!Индивидуальное домашнее задание №2. Массивы.
Найти в массиве натуральных чисел самое большое подмножество элементов, в котором любые два элемента имеют одинаковое множество простых делителей.

Индивидуальное домашнее задание №3. Функции.
Вычислить методом парабол интеграл , где . Сравнить полученное значение с интегралом функции на том же промежутке, вычисленным с помощью формулы Ньютона-Лейбница.

!!индивидуальное домашнее задание №4. Строки.
(В задачах этого раздела строки состоят из слов (последовательность букв) и знаков препинания (последовательность любых небуквенных символов).)

Найти в строке тройку слов таких, что из букв двух слов можно получить третье (при составлении этого слова следует использовать все буквы двух других). Если таких троек несколько, вывести ту, которая имеет максимальное суммарное количество букв.

Индивидуальное домашнее задание №5. Файлы.
(В задачах данного раздела следует считать, что в начале файла указано количество объектов, о которых идет речь в заданиях. Это позволяет после открытия файла создать динамический массив нужного размера.)

Файл содержит координаты некоторого множества точек плоскости. Выписать уравнение прямой, разделяющей плоскость на две полуплоскости, содержащие равное количество точек из заданного набора или сообщить, что такой прямой не существует.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ПолинаФ
2 / 2 / 0
Регистрация: 08.12.2010
Сообщений: 7
12.12.2010, 17:31  [ТС]     задачи на основные темы, требующие как минимум присутствие логики #2
подскажите пожалуйста хотя бы псевдокодом, а то я даже не знаю как это сделать на русском языке)))
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
13.12.2010, 00:10     задачи на основные темы, требующие как минимум присутствие логики #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Хорошие задачки. Давно такого здесь не было.
Начнем пока с конца.
Номер 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. Только вместо делителей - буквы. Хотя и есть и свои особенности
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,653
13.12.2010, 02:30     задачи на основные темы, требующие как минимум присутствие логики #4
#4
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//////////////////////////////////////////////////////////////////////////////////////
//!!индивидуальное домашнее задание №4. Строки.
//(В задачах этого раздела строки состоят из слов (последовательность букв) 
//и знаков препинания (последовательность любых небуквенных символов).)
 
//Найти в строке тройку слов таких, что из букв двух слов можно получить третье 
//(при составлении этого слова следует использовать все буквы двух других). 
//Если таких троек несколько, вывести ту, которая имеет максимальное суммарное 
//количество букв.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string                T_str;
typedef std::vector<T_str>         T_words;
typedef std::map<size_t, T_words>  T_3_words_map;
//////////////////////////////////////////////////////////////////////////////////////
T_words  get_words(const T_str&  s)
{
    T_str  s_new;
    std::transform(s.begin(), s.end(), std::back_inserter(s_new), tolower);
    
    std::replace_if(s_new.begin(), s_new.end(), std::not1(std::ptr_fun(isalpha)), ' ');
 
    std::istringstream  ssin(s_new);
    
    T_words  words;
    std::copy
        (
            std::istream_iterator<T_str>(ssin), 
            std::istream_iterator<T_str>(),           
            std::back_inserter(words)
        );
 
    return  words;
}
//////////////////////////////////////////////////////////////////////////////////////
size_t  get_3_words_total_size(const T_words&  words)
{
    return  words[0].size() + words[1].size() + words[2].size();   
}
//////////////////////////////////////////////////////////////////////////////////////
bool  word_is_made_of_2_words_letters(const T_words&  _3_words)
{
    T_str  A_str(_3_words[0]);
    T_str  B_str(_3_words[1] + _3_words[2]);
    
    std::sort(A_str.begin(), A_str.end());
    std::sort(B_str.begin(), B_str.end());
    return  A_str == B_str;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_3_words(const T_words&  words)
{
    T_3_words_map  _3_words_map;    
    for(T_str::size_type  i = 0; i < words.size(); ++i)
    {        
        for(T_str::size_type  j = 0; j < words.size(); ++j)
        {
            if(j == i) continue;     
            for(T_str::size_type  k = 0; k < words.size(); ++k)
            {
                if(   k == i
                   || k == j) continue;
 
                T_words  _3_words;
                _3_words.push_back(words[i]);
                _3_words.push_back(words[j]);
                _3_words.push_back(words[k]);                
                
                if(word_is_made_of_2_words_letters(_3_words))
                {                    
                    _3_words_map[get_3_words_total_size(_3_words)] = _3_words;
                }              
            }        
        }    
    }
    if(_3_words_map.empty())
    {
        std::cout << "В заданной строке нет слова, состоящего из букв двух других."
                  << std::endl;
    }
    else
    {
        std::cout << "В заданной строке слово \""
                  << _3_words_map.rbegin()->second[0]
                  << "\" состоит из букв слов \""
                  << _3_words_map.rbegin()->second[1]
                  << "\" и \""
                  << _3_words_map.rbegin()->second[2]
                  << "\"."
                  << std::endl;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите строку из латинских букв, разделенную на слова не латинскими буквами:"    
              << std::endl;
 
    T_str  s;
    getline(std::cin, s);    
    print_3_words(get_words(s));
}
ПолинаФ
2 / 2 / 0
Регистрация: 08.12.2010
Сообщений: 7
13.12.2010, 06:07  [ТС]     задачи на основные темы, требующие как минимум присутствие логики #5
большое спасибо, что откликнулись, теперь мне хоть немного логика понятна, буду писать)))
ПолинаФ
2 / 2 / 0
Регистрация: 08.12.2010
Сообщений: 7
22.12.2010, 19:31  [ТС]     задачи на основные темы, требующие как минимум присутствие логики #6
это код к задаче № 5
в нем рассмотрены частные случаи, подскажите пожалуйста как сделать в том случае если отдельные координаты некоторых точек совпадут, мне в ответе хорошо объяснили, но к сожалению как это реаизовать я не знаю, очень прошу помогите)))


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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>;
#include <fstream>;
using namespace std;
 
int search (int n)
{int m;
if (n%2==0) m=n/2;
else m=n/2+1;
return m;
}
 
void selection (int *mas,int n)
{
int m;
for (int i=0;i<n-1;i++)
{int min=mas[i];m=i;
    for (int j=i+1;j<n;j++)
    {int r=mas[j];
    if (r<min) {min=r;m=j;}
    }
mas[m]=mas[i];
mas[i]=min;
}
}
 
bool razn (int *mas,int n)
{int r,sch=0;
bool q=true;
for (int i=0;i<n;i++)
    {r=mas[i];
for (int j=i+1;j<n;j++)
    if (r==mas[j]) {q=false; sch+=1;}
};
return q;
}
 
int schet (int *mas,int n)
{int r,sch=0;
bool q=true;
for (int i=0;i<n;i++)
    {r=mas[i];
for (int j=i+1;j<n;j++)
    if (r==mas[j]) {q=false; sch+=1;}
};
return sch;
}
 
void main() {
double z;
int n,b,s,min,ch,Ay=100,By=-100,spy=0,soy=0;
ifstream fin;
fin.open("Dano.txt");
fin>>n;
cout<<n<<endl;
int flag=0;
int *masy;
masy=new int [n];
int *masx;
masx=new int [n];
int *mas;
mas=new int [(n*(n-1)/2)];
int k=0,h=0;
for (int j=0;j<n*2;j++){
    if (flag==1){
        fin>>ch;
        masy[k]=ch;
        k++;
        flag=0;
        }
    else
    {
    fin>>ch;
    masx[h]=ch;
    flag=1;
    h++;
    }
}
 
selection (masy,n);
selection (masx,n);
 
if (razn (masy,n))
{
s=search (n);
    if (n%2==0)
    {
        if ((masy[s-1]-masy[s])%2==0) z=(masy[s]-masy[s+1])/2;
        else z=(masy[s-1]-masy[s])/2+0.5;
    }
    else z=masy[s-1];
cout<<"y="<<z;
}
else
{
if (razn (masx,n))
{
s=search (n);
    if (n%2==0)
    {
        if ((masx[s-1]-masx[s])%2==0) z=(masx[s]-masx[s+1])/2;
        else z=(masx[s-1]-masx[s])/2+0.5;
    }
    else z=masx[s-1];
cout<<"x="<<z;
}
else 
{
cout<<"прямой нет";
 
}
}
fin.close();
cin>>b;
}
 Комментарий модератора 
Используйте теги форматирования кода.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
24.12.2010, 22:19     задачи на основные темы, требующие как минимум присутствие логики #7
ПолинаФ
Чтож, если сказал А, приходится и Б говорить
В твоих кодах я разбираться не стал, не потому что они не хороши, а просто
легче самому все сделать, чем пытаться понять, чего хочет твой собеседница
Тем более, что алгоритм я переделал, несколько упростил, тут мне моя собачка
помогла, гуляли мы с ним по легкому морозцу...
Ему - отдельное от тебя спасибо, кстати, зовут его - Байт.

Нам же надо чего? Найти прямую, которая не будет параллельна ни одному из
векторов, проведенных меж двумя нашими точками. Таких прямых много -
континуум. А нам всего-то одну найти.
Значит, считаем все эти вектора, и среди бесконечного множества других
векторов ищем с ними не совпадающий. А потом думаем, куда б его поместить.
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
65
66
67
68
69
// #include <stdlib.h>
#include <alloc.h>
#include <stdio.h>
#include <string.h>
 
cm(double *T1, double *T2)  // Функция сортировки
{
  if (*(T1+2) < *(T2+2)) return(-1);
  if (*(T1+2) > *(T2+2)) return(1);
  return(0);
}
/***********/
main()
{
  double *T, *V, vx, vy, d, A, x0, y0; FILE *f;
  char b[100]; // Буфер для ввода строк из файла
  int N, i, j, k; char *p;
 
  f = fopen("x.dat", "r"); // Файл с данными
  if (f==NULL) return;
  fgets(b, 10, f);
  N = atoi(b);  // Кол-во точек
  T = malloc(N*3*sizeof(double));  // Такая у него структура:
                         // T[3*i] - X точки, T[3*i+1] - ее Y
                         // T[3*i+2] - там потом будет расстояние до прямой
  for(i=0; i<N; i++) { // Вводим координаты точек
    fgets(b, 99, f);
    T[3*i] = atoi(b);
    p = strchr(b, ' ');
    T[3*i+1] = atoi(p);
  }   // В файле первая координата прижата влево, вторая - в той хе строчке через пробел
  fclose(f);
  V = malloc(N*(N-1)*sizeof(double)/2); // А это будут вектора
  for(i=0, k=0; i<N; i++) {
    for(j=i+1; j<N; j++, k++) {
       vx = T[3*i] - T[3*j];
       vy = T[3*i+1] - T[3*j+1];
       if (vx!=0) d = vy / vx;
       else       d = 0; // Это значит, что вектор || oY, но нас это не волнует
       V[k] = d;
    }
  }
  A = 0.1;
  while(1) { // Ищем неиспользованное направление. Найдем навярняка.
             // У нас в запасе - бесконечность!
    for(i=0; i<N*(N-1)/2; i++) if (A==V[i]) break;
    if (i==N*(N-1)/2) A += 0.1;
    else break;
  }
    // Прямая A*x - y = 0 не параллельна ни одному из векторов
  for(i=0; i<N; i++) {
    d = A*T[3*i] - T[3*i+1];  // Расстояние от точки до этой прямой
    T[3*i+2] = d;
  }
  qsort(T, N, 3*sizeof(double), cm); // Сортировка
  if (N%2) {    // N - нечетное. x0, y0 - средняя точка
    k = N/2 + 1;
    x0 = T[3*k];
    y0 = T[3*k+1];
  }
  else {  // N - четное. x0, y0 - Точка между двумя средними
    k = N/2;
    x0 = (T[3*k] + T[3*k-3])/2;
    y0 = (T[3*k+1] + T[3*k-2])/2;
  }
  printf("Уравнение прямой\n");
  printf("Y-%f = %f(X-%f)\n", y0, A, x0);
}
/*************/
Программу я не проверял - только на синтаксис. Если что не так - работай!
По поводу "возможности / невозможности", если считать полуплоскости с краями,
то задача разрешима ВСЕГДА.
Ежели без краев, надо в уравнение полученной прямой подставлять точки,
считать сколько с плюсом, сколько с минусом, и если не равно - Увы!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.12.2010, 11:40     задачи на основные темы, требующие как минимум присутствие логики
Еще ссылки по теме:

C++ Двумерные массивы Найти минимум получить новую матрицу деленные на минимум
Сканирование компьютеров на присутствие в сети онлайн. #threads #c++11 #ping #icmp C++
C++ Как детектировать присутствие пробела в строке? Regex

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

Или воспользуйтесь поиском по форуму:
Байт
 Аватар для Байт
13954 / 8785 / 1221
Регистрация: 24.12.2010
Сообщений: 15,894
25.12.2010, 11:40     задачи на основные темы, требующие как минимум присутствие логики #8
Day, по поводу "ВСЕГДА" ты, кажется, погорячился.
Пример. N=5. 2-я и 3-я точки (в твоей упорядоченности) слиплись (их координаты тождественны)
Что не исключает того, что есть другое направление разбивающей прямой, с которым все будет хорошо.
Конкретный пример невозможности разбиения:
(0,0) (1,0) (1,0) (2,0) (3,0)
Т.е. если допустить совпадение некоторых точек, задачка оказывается сложнее, чем ты ожидал.
Но если предположить, что все точки РАЗНЫЕ, твое решение вполне удовлетворительно.
Yandex
Объявления
25.12.2010, 11:40     задачи на основные темы, требующие как минимум присутствие логики
Ответ Создать тему
Опции темы

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