Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.64/83: Рейтинг темы: голосов - 83, средняя оценка - 4.64
1 / 1 / 0
Регистрация: 19.11.2010
Сообщений: 10

Построить ломаную по заданным вершинам

23.08.2011, 10:46. Показов 18633. Ответов 40

Студворк — интернет-сервис помощи студентам
Помогите решить несколько задач по Си:

1.Дан файл f, компоненты которого являются целыми числами. Найти:количество квадратов нечетных чисел среди компонент.

2.Дан текстовый файл f. Записать в перевернутом виде строки файла f в файл g. Порядок строк в файле g должен быть обратным по оношению к порядку строк исходного файла.

3.Построить ломаную по заданным вершинам. Вершины указываются с клавиатуры (см. задачу 900).

задача 900:При работе с графическим изображением часто возникает необходимость выбрать одну или несколько точек экрана. Так, например, для того чтобы построить отрезок, следует задать два его конца, для построения окружности можно задать ее центр и любую точку на окружности и т. д. Для указывания требуемой точки обычно используют курсор. Курсор может иметь одну, из следующих конфигураций:
а) Перекрестье (рис. 95, а). Указываемая точка-это точка пересечения двух прямых.
б) Крестик (рис. 95,6). Указываемая точка-это точка пересечения двух коротких отрезков.
в) Стрелка (рис. 95, б). Указываемая точка-это точка, в которую помещается острие стрелки.
1
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
23.08.2011, 10:46
Ответы с готовыми решениями:

Дано n точек на плоскости, за время n*logn построить (n-1)-звенную ломаную
Дано n точек на плоскости, заданных своими декартовыми координатами. За время n*logn построить (n-1)-звенную не пересекающую себя ломаную,...

За время n logn построить (n-1)звенную не пресекающую себя ломаную проходящую через все точки
Дано n точек на плоскости заданных своими декартовыми координатами. За время n logn построить (n-1)звенную не пресекающую себя ломаную...

Дано 20 натуральных чисел. Каждая пара чисел определяет положение вершины ломаной на экране. Построить ломаную
а можно эту программу в с++? спасибо

40
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
23.08.2011, 14:20
Студворк — интернет-сервис помощи студентам
Прежде чем каким-либо образом вычислять корень или проводить разложение, стоит сделать простую проверку, которая отсеит 87,5% чисел:
C
1
2
3
4
if (x % 8 != 1) // или (x & 7 != 1)
{
    // x is not square of odd
}
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
23.08.2011, 14:23
Цитата Сообщение от grizlik78 Посмотреть сообщение
Прежде чем каким-либо образом вычислять корень или проводить разложение, стоит сделать простую проверку, которая отсеит 87,5% чисел:
C
1
2
3
4
if (x % 8 != 1) // или (x & 7 != 1)
{
    // x is not square of odd
}
А доказать сможете?
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
23.08.2011, 14:28
Лучший ответ Сообщение было отмечено как решение

Решение

Конечно.
Но я даже больше скажу. Последовательность квадратов нечётных чисел можно получить такой рекуррентной формулой:
https://www.cyberforum.ru/cgi-bin/latex.cgi?x_i = x_{i-1}+8i

https://www.cyberforum.ru/cgi-bin/latex.cgi?x_0 = 1

Добавлено через 2 минуты
Но проверка не позволяет распознать числа, которые точно являются квадратами нечётных. Она позволяет распознать числа, которые точно такими квадратами не являются. Дальше пока не придумывается
3
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
23.08.2011, 14:35
Цитата Сообщение от grizlik78 Посмотреть сообщение
Конечно.
Но я даже больше скажу. Последовательность квадратов нечётных чисел можно получить такой рекуррентной формулой:
https://www.cyberforum.ru/cgi-bin/latex.cgi?x_i = x_{i-1}+8i

https://www.cyberforum.ru/cgi-bin/latex.cgi?x_0 = 1
Что-то знакомое очень, не помню откуда. Правда вы не доказали, что эта последовательность исчерпывает все нужные числа (или ссылки не дали), Но все равно спасибо.
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
23.08.2011, 14:42
Ну да, я сказал, что могу, но не доказывал
Если число x является квадратом нечётного, то можно его записать так:
https://www.cyberforum.ru/cgi-bin/latex.cgi?x^2 = (2a+1)^2 = 4a^2 + 4a + 1
откуда видно, что
https://www.cyberforum.ru/cgi-bin/latex.cgi?4 | (x^2 - 1)
и при этом
https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{x^2 - 1}{4}=a(a+1)
то есть
https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{x^2 - 1}{8}=\frac{a(a+1)}{2}
Справа сумма арифметической прогрессии, откуда несложно и рекуррентную формулу вывести.
2
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
23.08.2011, 15:08
grizlik78, доказательство очевидное

Добавлено через 1 минуту
Можно проще:
https://www.cyberforum.ru/cgi-bin/latex.cgi?(2i+1)^2-(2i-1)^2=8i

Добавлено через 25 минут
Deviaphan, ваш метод лучше моего, корни на аппаратном уровне в сотни раз быстрее вычисляются, чем самое оптимальное программное разложение.
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
23.08.2011, 15:16
Цитата Сообщение от Olga_ Посмотреть сообщение
ваш метод лучше моего
В своё оправдание могу сказать, что я ни разу математики не знаю и разложения просто не смог бы сделать.) Надо восполнять пробелы... пошёл читать.)
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
23.08.2011, 15:18
Но такой метод подходит только для процессоров, где есть аппаратный корень и плавучка. Хотя ТС вроде не ограничивали заданием
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
23.08.2011, 15:21
Цитата Сообщение от grizlik78 Посмотреть сообщение
где есть аппаратный корень
x87 и старше
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
23.08.2011, 15:22
Цитата Сообщение от grizlik78 Посмотреть сообщение
Но такой метод подходит...
А если абстрагироваться от аппаратуры, вот Вы каким бы методом проверяли?
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
23.08.2011, 16:03
Цитата Сообщение от Deviaphan Посмотреть сообщение
x87 и старше
x87 не процессор
Но я в курсе современного состояния дел, спасибо. А так же в курсе, что кроме настольных ПК есть ещё и микроконтроллеры всякие, и сигнальники без FPU...

Добавлено через 40 минут
Цитата Сообщение от Olga_ Посмотреть сообщение
А если абстрагироваться от аппаратуры, вот Вы каким бы методом проверяли?
Да вот чёрт знает. Если возможность есть, то аппаратное бы использовал, наверное, а если нет...
Методов-то хороших как-то не очень видно. Попробовал бы методом Ньютона, ну вон Герона ещё можно, хотя как-то не кажется удачным, ну и своё что-нибудь попытался бы изобрести. Дня два
0
1 / 1 / 0
Регистрация: 19.11.2010
Сообщений: 10
23.08.2011, 16:04  [ТС]
Юра, предпочтение Си. Строить по точкам с клавиатуры в консоле. Большое спасибо=))
0
Автор FAQ
 Аватар для -=ЮрА=-
6614 / 4256 / 401
Регистрация: 08.08.2009
Сообщений: 10,325
Записей в блоге: 24
23.08.2011, 16:10
Цитата Сообщение от chulkov-93 Посмотреть сообщение
Юра, предпочтение Си. Строить по точкам с клавиатуры в консоле. Большое спасибо=))
- принял в работу, ближе к вечеру выложу исходник!До связи...
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
23.08.2011, 16:11
Цитата Сообщение от grizlik78 Посмотреть сообщение
x87 не процессор
сопроцессор. А в более старших моделях уже интегрировано (если не ошибаюсь.)
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
24.08.2011, 03:05
Цитата Сообщение от grizlik78 Посмотреть сообщение
ну вон Герона ещё можно, хотя как-то не кажется удачным
А вообще-то я тут подумал... Вроде очень даже ничего методом Герона получается.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int is_square_of_odd(int a)
{
    int x = 1, b = a;
    if (a % 8 != 1)
        return 0;
 
    while (b > 3)
    {
        b /= 4;
        x <<= 1;
    }
 
    while (abs(a - x*x) >= 2*x)
        x = (x + a/x) / 2;
 
    return a == x*x || a == (x-1)*(x-1);
}
Возможно выражение в цикле и в возврате можно упростить, но и так уже довольно неплохо.

Добавлено через 9 часов 36 минут
Цитата Сообщение от grizlik78 Посмотреть сообщение
Попробовал бы методом Ньютона, ну вон Герона ещё можно
Забавно то, что итерационная формула Герона это, похоже, и есть итерационный метод Ньютона
На моих компьютерах этот метод работает в среднем в 2 раза медленней, чем с использованием sqrt(). Зато не используется арифметика с плавающей точкой. Ещё бы и без деления обойтись. Эх...
Ну и на всякий случай вариант с sqrt(), хотя он и банальный.
C
1
2
3
4
5
6
7
8
9
int is_square_of_odd(int a)
{
    int x;
    if (a % 8 != 1)
        return 0;
 
    x = sqrt(a);
    return a == x*x;
}
1
Автор FAQ
 Аватар для -=ЮрА=-
6614 / 4256 / 401
Регистрация: 08.08.2009
Сообщений: 10,325
Записей в блоге: 24
24.08.2011, 03:16
chulkov-93 , консоль готова, пока выкладываю скриншот, а код уж завтра(всем кто хочет его сейчас посмотреть пока скажу нет (код нужно привести в божеский вид, т.к. там комент на коменте - кодил в поте лица)
Миниатюры
Построить ломаную по заданным вершинам  
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
24.08.2011, 06:10
Цитата Сообщение от grizlik78 Посмотреть сообщение
Ещё бы и без деления обойтись. Эх.
Деление на 2 и 4 это сдвиги вправо на 1 и 2 бита соответственно. %8 эквивалентен &7.
0
1 / 1 / 0
Регистрация: 19.11.2010
Сообщений: 10
24.08.2011, 10:15  [ТС]
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
chulkov-93 , консоль готова, пока выкладываю скриншот, а код уж завтра(всем кто хочет его сейчас посмотреть пока скажу нет (код нужно привести в божеский вид, т.к. там комент на коменте - кодил в поте лица)
Огромное вам спасибо=)))
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
24.08.2011, 11:39
Цитата Сообщение от Deviaphan Посмотреть сообщение
Деление на 2 и 4 это сдвиги вправо на 1 и 2 бита соответственно. %8 эквивалентен &7.
Спасибо, но я, конечно же, имел в виду деление на x. Всё остальное компилятор умеет заменять.
0
Автор FAQ
 Аватар для -=ЮрА=-
6614 / 4256 / 401
Регистрация: 08.08.2009
Сообщений: 10,325
Записей в блоге: 24
24.08.2011, 13:32
Лучший ответ Сообщение было отмечено как решение

Решение

Итак, выкладываю код (т.к отлов мыши в консоли - довольно непростое дело, то функцию getMouseClick запихнул в DLL выкладываю также скомпилированные и работоспособные MClick.exp
MClick.lib и MClick.DLL - они должны быть в папке проекта!!!). С графикой намного легче, поэтому запихивать в DLL не стал, думаю суть задания была научиться по координатам щелчка стоить линию, а не вникать в суть доступа к потоку консоли STD_INPUT и STD_OUTPUT!Если же есть особое желание создать MClick.DLL, то советую раскопать использование следующих функций
C++
1
2
SetConsoleMode
ReadConsoleInput
и данных в структуре
C++
1
MOUSE_EVENT_RECORD

Пара слов о функции масштабирования координат щелчка - имей в виду что координаты щелчка идут как текстовые коодинаты консоли, т.е напрямую зависят от разрешения экрана и некоторых настроек в системе, поэтому для перевода в привычные координаты нужно вводить масштабные коэффициенты - это
i
C++
1
2
3
4
5
nt nROWS = 25;
    int nCOLS = 80;
 
    double CX = (pRECT.right - pRECT.left)/nCOLS;
    double CY = (pRECT.bottom - pRECT.top)/nROWS;
И не забыть сдвинуть мышь на величину заголовка окна и ширину его раниц, на сим желаю приятного использования данного приложения!
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
115
116
117
118
119
120
121
122
#include <windows.h>
#include <stdio.h>
 
#define IMPORT __declspec (dllimport)
#pragma comment(lib,"MClick.lib") //Подключаем MClick.lib
//Функция импортируемая из DLL
IMPORT DWORD getMouseClick(HANDLE hSTD_IN, COORD &POS); 
//Возвращаемые значения POS - координаты щелчка мыши
//(в символьных координатах консоли - это ВАЖНО!)
//DWORD reurn :
//FROM_LEFT_1ST_BUTTON_PRESSED - 1-слева кнопка (ЛЕВАЯ)
//FROM_LEFT_2ND_BUTTON_PRESSED - 2-слева кнопка (СРЕДНЯЯ, если есть)
//FROM_LEFT_3RD_BUTTON_PRESSED - 3-слева кнопка (доп кнопка 1, если есть)
//FROM_LEFT_4TH_BUTTON_PRESSED - 4-слева кнопка (доп кнопка 2, если есть)
//RIGHTMOST_BUTTON_PRESSED     - правая кнопка  (ПРАВАЯ)   
 
#define RED RGB(255,0,0)
#define GRN RGB(0,255,0)
#define BLU RGB(0,0,255)
 
#define BLK RGB(0,0,0)
#define WHT RGB(255,255,255)
 
HPEN getPen(int iPEN_STYLE, int iPEN_SIZE, int iCOLORREF);
BOOL SetPoint(HDC hDC, HPEN hPen, COORD PNT);
BOOL PlotLine(HDC hDC, HPEN hPen, COORD BGN, COORD END);
 
COORD setCordScale(COORD POS, RECT pRECT);
 
int main()
{
    SetConsoleOutputCP(1251);
    HWND   hWnd     = GetForegroundWindow();
    HANDLE hSTD_IN  = GetStdHandle(STD_INPUT_HANDLE);
    HANDLE hSTD_OUT = GetStdHandle(STD_OUTPUT_HANDLE);
 
    HPEN    LPEN = getPen(PS_SOLID, 2, RED);
    HPEN    PPEN = getPen(PS_SOLID, 3, WHT);
    RECT    pRECT= {0};
    COORD   POS  = {0};
    DWORD   dwCLICK = NULL;
    GetWindowRect(hWnd,&pRECT);
    COORD   BGN  = setCordScale(POS,pRECT);
    HDC hDC = GetWindowDC(hWnd);
    if(hDC)
    {
        SetBkMode(hDC,TRANSPARENT);//Можно и не устанавливать єтот режим, но с ним ярче
        SetPoint (hDC, PPEN, BGN);
        do
        {
            GetWindowRect(hWnd,&pRECT);
            if((dwCLICK = getMouseClick(hSTD_IN,POS)) == RIGHTMOST_BUTTON_PRESSED)
            {
                //Очистка экрана
                ShowWindow(hWnd,SW_HIDE);
                PlotLine(hDC, LPEN, BGN,  BGN);
                ShowWindow(hWnd,SW_SHOW);
            }
            POS = setCordScale(POS,pRECT);
            PlotLine(hDC, LPEN, BGN,  POS);
            SetPoint(hDC, PPEN, BGN = POS);
        }
        while(dwCLICK != FROM_LEFT_2ND_BUTTON_PRESSED);
    }
    system("pause");
    return 0;
}
 
HPEN getPen(int iPEN_STYLE, int iPEN_SIZE, int iCOLORREF)
{
    return CreatePen(iPEN_STYLE, iPEN_SIZE, iCOLORREF);
}
 
BOOL SetPoint(HDC hDC, HPEN hPen, COORD PNT)
{
    EXTLOGPEN pINFO;
    GetObject(hPen,sizeof(EXTLOGPEN),&pINFO);
    SelectObject(hDC,hPen);
    return Ellipse
    (
        hDC,
        PNT.X - pINFO.elpWidth,
        PNT.Y + pINFO.elpWidth, 
        PNT.X + pINFO.elpWidth,
        PNT.Y - pINFO.elpWidth
    );
}
 
BOOL PlotLine(HDC hDC, HPEN hPen, COORD BGN, COORD END)
{
    SelectObject(hDC,hPen);
    MoveToEx(hDC,BGN.X,BGN.Y,NULL);
    return LineTo(  hDC,END.X,END.Y);
}
 
COORD setCordScale(COORD POS, RECT pRECT)
{
    if(POS.X == 0)
        POS.X = 1;
    if(POS.Y == 0)
        POS.Y = 1;
 
    int nROWS = 25;
    int nCOLS = 80;
 
    double CX = (pRECT.right - pRECT.left)/nCOLS;
    double CY = (pRECT.bottom - pRECT.top)/nROWS;
 
    //При текстовом режиме(text mode) экран  делится  на  ячейки
    //(80  или 40 колонок в ширину и 25 строк в высоту)
    POS.X *= CX;
    POS.Y *= CY;
 
    int xBORDER = GetSystemMetrics(SM_CXBORDER);//Ширина границы окна
    int yBORDER = GetSystemMetrics(SM_CYMENU);  //Высота заголовка окна ~= высоте строк меню
    int xDRAG   = GetSystemMetrics(SM_CXDRAG);  //Число пикселей на гориз дрожение мыши
    int yDRAG   = GetSystemMetrics(SM_CYDRAG);  //Число пикселей на вертик дрожение мыши
 
    POS.X += xBORDER + xDRAG;//Ширина границы окна + число пикселей на дрожение мыши
    POS.Y += yBORDER + yDRAG;
    return POS;
}
PS:Если есть необходимость очистить экран от линии щелков, то жмём правую клавишу мыши...
Миниатюры
Построить ломаную по заданным вершинам  
Вложения
Тип файла: rar console_mouse_project.rar (28.6 Кб, 325 просмотров)
6
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
24.08.2011, 13:32

Нарисовать треугольник по заданным вершинам
В декартовой системе заданы три координаты вершин треугольника, по этим координатам нарисовать на экране треугольник. Заранее спасибо!

По заданным вершинам определить фигуру
квадрат, прямоугольник, параллелограмм, трапеция или ромб. Необходимо написать консольное приложение Добавлено через 1 минуту uses...

Вычисление объема тетраэдра по заданным вершинам
Вычислить объем тетраэдра по заданным вершинам (координаты на Ваше усмотрение). Заранее спасибо.

Постройте ломаную линию по заданным точкам
На плоскости заданы n точек своими координатами. Постройте ломаную линию, проходящую через эти точки, причем через каждую точку ломаная...

Определить, какой из треугольников, построенных по заданным вершинам, имеет наибольшую площадь
Сегодня в институте дали задание по дисциплине &quot;Информатика и программирование&quot; но к нашему же сожалению мы не прошли ту тему на...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался)))
anaschu 30.06.2026
Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .
сукцессия 16. Общий обзор, в основном что бы другие ии поняли
anaschu 29.06.2026
# Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru