Перейти из форума на сайт.

НовостиФайловые архивы
ПоискАктивные темыТоп лист
ПравилаКто в on-line?
Вход Забыли пароль? Первый раз на этом сайте? Регистрация
Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Задачи по C/С++

Модерирует : ShIvADeSt

 Версия для печати • ПодписатьсяДобавить в закладки
Страницы: 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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389

Открыть новую тему     Написать ответ в эту тему

de_lirium

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Тема создана для накопления реализаций типовых задач на С/С++.
Прежде чем публиковать своё условие задачи, убедитесь, что её решение (или решение очень похожей задачи) в теме и полезных ссылках отсутствует (например воспользуйтесь ссылкой Версия для печати вверху справа страницы и поищите в ней).
Постарайтесь как можно полнее сформулировать постановку задачи (чтобы тому, кто решит вам помочь, не приходилось тратить своё время ещё и на выпытывание у вас деталей условия; если вам не понятно, как это сделать - постарайтесь представить, что эта программа у вас уже есть, и "поработать" с ней - вот все детали, которые при этом придут в голову, с большой вероятностью должны быть в условии задачи).
Если вы уже пытались сделать эту задачу, но у вас не получилось и вы хотите довести дело до конца - обязательно выложите результат своей попытки, предварительно убедившись, что ваш код компилируется.

Вопросы по технологиям лучше задавать тут.

Прежде чем просить помощи в задании...
Если позарез надо и вы даже готовы заплатить

Если вам вдруг не отвечают или ответ вас не устраивает, и вообще полезно прочитать всем спрашивающим.

Полезные ссылки:
 
C++: в том числе и решения задач (eng)
задачи на C
 
Проверить свою задачку можно:
Онлайн-компилятором Visual C++
godbolt
Wandbox
Одним из онлайн-компиляторов на ideone.com

Всего записей: 28 | Зарегистр. 23-07-2004 | Отправлено: 02:14 20-12-2004 | Исправлено: Daniyar91, 19:25 27-09-2017
Mickey_from_nsk

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
graycrow
Ну еще - через структуры

Всего записей: 636 | Зарегистр. 21-10-2002 | Отправлено: 14:22 15-11-2006
Drol



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Здравствуйте
Есть простая Задача, но в задаче, указано, что программа должна начать и завершить за 2000 милисекунд (за 2 секунды). Помогите решить задачу....
 
Описание задачи
Problem D. Двумерная статистика Time Limit: 2000 ms Memory Limit: 16 MB
На плоскости заданы N различных точек и M прямоугольников со сторонами параллельными осям координат. Для каждого прямоугольника вывести количество точек, находящихся внутри этого прямоугольника.  
Input В первой строке два целых числа N (0 < N <= 20000) и M (0 < M <= 20000). Далее следуют N строк, каждая из которых содержит координаты одной точки - два целых числа X[i] и Y[i]. Далее следуют M строк, описывающих прямоугольники. Каждый прямоугольник задается координатами левой-нижней веришины Xlb[i] и Ylb[i] и правой-верхней вершины Xrt[i] (Xlb[i] <= Xrt[i]) и Yrt[i] (Ylb[i] <= Yrt[i]). Все координаты в интервале [0; 100000].  
 
Output Вывести M строк, в i-той строке должно содержаться одно целое число - количество точек внутри i-го прямоугольника.
 
Sample input I
4 2
0 0
1 1
2 0
0 2
0 0 2 2
2 2 3 3  
 
Sample output I
4
0  
 
Примечание: ваше решение должно быть основано на эффективном алгоритме, иначе оно превысит лимит времени.
---
 
Мной программно написаное, только когда оно данные обрабатывает максимум 20000 точек И 20000 прямоугольников, оно завершает выполнения задачи больше 2000 мс (2 сек).
//ds.cpp
#include <stdio.h>
int main()
{
int tob,pob,j,p[4];;
int tc[20000][2];
int pr[20000];
scanf("%i%i",&tob,&pob);
for (register int i=0; i<tob; ++i) scanf("%i%i",&tc[i][0],&tc[i][1]);
for (register int i=0; i<pob; ++i)
{
    scanf("%i%i%i%i",&p[0],&p[1],&p[2],&p[3]);
    pr[i]=0;
    for (j=0;j<tob;++j)
            if (tc[j][0]>=p[0] && tc[j][0]<=p[2]  
                && tc[j][1]>=p[1] && tc[j][1]<=p[3]) ++pr[i];
}
for (register int i=0; i<pob; ++i)  printf("%i\n",pr[i]);
return(0);
}
-----
P.S. Чтобы в ручную не писать 20000 точек и 20000 прямоугольков воспользуйтесь программой "Random.cpp", которая создает случайным образом в файле "inp.txt"  в количество 20000. Скомпилируйте Random.cpp и ds.cpp (тело программы написано на верху). После создайте файл "test.bat", тело описано внизу. Программа "test.bat" автоматически создает случайные точки в файл "inp.txt", после возмет ввод данных с "inp.txt" и выведет результат в файл в "out.txt". Так же автоматически покажен восколько начала программа работать и восколько завершила.  Запустив cmd.exe - ДОС среде напишите "test.bat".  
Надейюсь есть кто сможет решить задача, которая затрата времени на выполнения не привышало 2000 мс (2 сек).
1)  // Random.cpp  
#include <stdio.h>
#include <iostream.h>
int main()
{
int xx1,yy1,xx2,yy2;
int x1,y1,x2,y2;
cout<<"20000 20000";
randomize();
for (register int i=0; i<20000; ++i) cout<<endl<<random(100000)<<" "<<random(100000);
for (register int i=0; i<20000; ++i)
{
xx1=random(100000);
yy1=random(100000);
xx2=random(100000);
yy2=random(100000);
if (xx1>=xx2) {x1=xx2;x2=xx1;} else {x1=xx1;x2=xx2;}  
if (yy1>=yy2) {y1=yy2;y2=yy1;} else {y1=yy1;y2=yy2;}  
 
cout<<endl<<x1<<" "<<y1<<" "<<x2<<" "<<y2;
}
return(0);
}
---
 
2) //test.bat
@Echo off
Random.exe >inp.txt
:t
if "%time:~9,2%" NEQ "00" goto t
echo Begin time - %time:~6,5%  sekund
ds.exe <inp.txt >out.txt
echo End time - %time:~6,5% sekund

Всего записей: 69 | Зарегистр. 26-09-2001 | Отправлено: 07:06 16-11-2006 | Исправлено: Drol, 11:59 16-11-2006
Mickey_from_nsk

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Мной программно написаное, только когда оно данные обрабатывает максимум 20000 точек И 20000 прямоугольников, оно завершает выполнения задачи больше 2000 мс (2 сек).  

Хммм... Если не секрет, а как засекалось время? Какая аппаратная и программная платформа? Какой компилятор, наконец, и опции компиляции?
Странные ограничения. Откуда они? Как в многозадачных системах можно уверенно гарантировать время выполнения задачи?

Всего записей: 636 | Зарегистр. 21-10-2002 | Отправлено: 09:25 16-11-2006
Drol



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Mickey_from_nsk  

Цитата:
Хммм... Если не секрет, а как засекалось время? Какая аппаратная и программная платформа? Какой компилятор, наконец, и опции компиляции?  
Странные ограничения. Откуда они? Как в многозадачных системах можно уверенно гарантировать время выполнения задачи?

 
Как они засекали я не в курсе. Я проверяю и тестирую, test.bat файлов, который на верх написал.
компилятор один из 4 языков VC++, Delphi, Java, C#
Говорят что у них есть решеная программа, которая успевает за 2 секунды совершить. Нужно использовать какой то алгоритм.
 
Я заметил что, при 10000 точек и 10000 примоугольника, программа совершает за 1 секунду.
Я применил алгорит на разделения на 2 части масива, то по 10000 и поверку прямоугольников на точки паральено включил.  
Так же пробывал за раз по 10 прямоугольников проверку на 1 точку.
Но покрайнем мере в отличии от простой верхней програмы алгоритмическии не много быстрее работает.
к примеру паралельно по 10 прямоугольников 1 точку проверка
#include <stdio.h>
int main()
{
int tob[2],pob[2];
int tc[20000][2];
int pr[20000][4];
int o[10],j,i;
scanf("%i %i",&tob[0],&pob[0]);
tob[1]=-1;pob[1]=-1;
if (tob[0]>9) {tob[1]=tob[0]/10;tob[1]=tob[1]*10;}
if (pob[0]>9) {pob[1]=pob[0]/10;pob[1]=pob[1]*10;}
 
// Ввод оптом по 20 или по 10 или 1 точек координат
o[0]=tob[1]-10;
for (i=0; i<tob[0]; ++i)  
{
    scanf("%i%i",&tc[i][0],&tc[i][1]);
    if (i<o[0])
        {
            scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i",
                &tc[i+1][0],&tc[i+1][1],      &tc[i+2][0],&tc[i+2][1],      &tc[i+3][0],&tc[i+3][1],
                &tc[i+4][0],&tc[i+4][1],      &tc[i+5][0],&tc[i+5][1],      &tc[i+6][0],&tc[i+6][1],
                &tc[i+7][0],&tc[i+7][1],      &tc[i+8][0],&tc[i+8][1],      &tc[i+9][0],&tc[i+9][1],
                &tc[i+10][0],&tc[i+10][1],  &tc[i+11][0],&tc[i+11][1],  &tc[i+12][0],&tc[i+12][1],
                &tc[i+13][0],&tc[i+13][1],  &tc[i+14][0],&tc[i+14][1],  &tc[i+15][0],&tc[i+15][1],
                &tc[i+16][0],&tc[i+16][1],  &tc[i+17][0],&tc[i+17][1],  &tc[i+18][0],&tc[i+18][1],
                &tc[i+19][0],&tc[i+19][1]
                );
            i=i+19;
        } else if (i<tob[1])
                {
                    scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i",
                        &tc[i+1][0],&tc[i+1][1],   &tc[i+2][0],&tc[i+2][1],
                        &tc[i+3][0],&tc[i+3][1],   &tc[i+4][0],&tc[i+4][1],
                        &tc[i+5][0],&tc[i+5][1],   &tc[i+6][0],&tc[i+6][1],
                        &tc[i+7][0],&tc[i+7][1],   &tc[i+8][0],&tc[i+8][1],
                        &tc[i+9][0],&tc[i+9][1]
                        );
                    i=i+9;
                }
}
 
// Ввод оптом по 20 или по 10 или 1 прямоугольника координат
o[0]=pob[1]-10;
for (i=0; i<pob[0]; ++i)
{
    scanf("%i%i%i%i",&pr[i][0],&pr[i][1],&pr[i][2],&pr[i][3]);
    if (i<o[0])
        {
            scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i",
                &pr[i+1][0],&pr[i+1][1],&pr[i+1][2],&pr[i+1][3],  &pr[i+2][0],&pr[i+2][1],&pr[i+2][2],&pr[i+2][3],
                &pr[i+3][0],&pr[i+3][1],&pr[i+3][2],&pr[i+3][3],  &pr[i+4][0],&pr[i+4][1],&pr[i+4][2],&pr[i+4][3],
                &pr[i+5][0],&pr[i+5][1],&pr[i+5][2],&pr[i+5][3],  &pr[i+6][0],&pr[i+6][1],&pr[i+6][2],&pr[i+6][3],
                &pr[i+7][0],&pr[i+7][1],&pr[i+7][2],&pr[i+7][3],  &pr[i+8][0],&pr[i+8][1],&pr[i+8][2],&pr[i+8][3],
                &pr[i+9][0],&pr[i+9][1],&pr[i+9][2],&pr[i+9][3],
                &pr[i+10][0],&pr[i+10][1],&pr[i+10][2],&pr[i+10][3],
                &pr[i+11][0],&pr[i+11][1],&pr[i+11][2],&pr[i+11][3],
                &pr[i+12][0],&pr[i+12][1],&pr[i+12][2],&pr[i+12][3],
                &pr[i+13][0],&pr[i+13][1],&pr[i+13][2],&pr[i+13][3],
                &pr[i+14][0],&pr[i+14][1],&pr[i+14][2],&pr[i+14][3],
                &pr[i+15][0],&pr[i+15][1],&pr[i+15][2],&pr[i+15][3],
                &pr[i+16][0],&pr[i+16][1],&pr[i+16][2],&pr[i+16][3],
                &pr[i+17][0],&pr[i+17][1],&pr[i+17][2],&pr[i+17][3],
                &pr[i+18][0],&pr[i+18][1],&pr[i+18][2],&pr[i+18][3],
                &pr[i+19][0],&pr[i+19][1],&pr[i+19][2],&pr[i+19][3]
                );
            i=i+19;
        } else if (i<pob[1])
                {
                    scanf("%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i",
                        &pr[i+1][0],&pr[i+1][1],&pr[i+1][2],&pr[i+1][3],
                        &pr[i+2][0],&pr[i+2][1],&pr[i+2][2],&pr[i+2][3],
                        &pr[i+3][0],&pr[i+3][1],&pr[i+3][2],&pr[i+3][3],
                        &pr[i+4][0],&pr[i+4][1],&pr[i+4][2],&pr[i+4][3],
                        &pr[i+5][0],&pr[i+5][1],&pr[i+5][2],&pr[i+5][3],
                        &pr[i+6][0],&pr[i+6][1],&pr[i+6][2],&pr[i+6][3],
                        &pr[i+7][0],&pr[i+7][1],&pr[i+7][2],&pr[i+7][3],
                        &pr[i+8][0],&pr[i+8][1],&pr[i+8][2],&pr[i+8][3],
                        &pr[i+9][0],&pr[i+9][1],&pr[i+9][2],&pr[i+9][3]
                        );
                    i=i+9;
                }
}
// Проверка прямоугольника с точками
for (i=0; i<pob[0]; ++i)
{   o[0]=0;o[1]=0;o[2]=0;o[3]=0;o[4]=0;o[5]=0;o[6]=0;o[7]=0;o[8]=0;o[9]=0;
    for (j=0;j<tob[0];++j)
    {
        if (tc[j][0]>=pr[i][0] && tc[j][0]<=pr[i][2] && tc[j][1]>=pr[i][1] && tc[j][1]<=pr[i][3]) ++o[0];
        if (i<pob[1])
           {  
        // проверка еще 9 прямоугольника при условии i<pob[1] иначе не проверяй
        if (tc[j][0]>=pr[i+1][0] && tc[j][0]<=pr[i+1][2] && tc[j][1]>=pr[i+1][1] && tc[j][1]<=pr[i+1][3]) ++o[1];
        if (tc[j][0]>=pr[i+2][0] && tc[j][0]<=pr[i+2][2] && tc[j][1]>=pr[i+2][1] && tc[j][1]<=pr[i+2][3]) ++o[2];
        if (tc[j][0]>=pr[i+3][0] && tc[j][0]<=pr[i+3][2] && tc[j][1]>=pr[i+3][1] && tc[j][1]<=pr[i+3][3]) ++o[3];
        if (tc[j][0]>=pr[i+4][0] && tc[j][0]<=pr[i+4][2] && tc[j][1]>=pr[i+4][1] && tc[j][1]<=pr[i+4][3]) ++o[4];
        if (tc[j][0]>=pr[i+5][0] && tc[j][0]<=pr[i+5][2] && tc[j][1]>=pr[i+5][1] && tc[j][1]<=pr[i+5][3]) ++o[5];
        if (tc[j][0]>=pr[i+6][0] && tc[j][0]<=pr[i+6][2] && tc[j][1]>=pr[i+6][1] && tc[j][1]<=pr[i+6][3]) ++o[6];
        if (tc[j][0]>=pr[i+7][0] && tc[j][0]<=pr[i+7][2] && tc[j][1]>=pr[i+7][1] && tc[j][1]<=pr[i+7][3]) ++o[7];
        if (tc[j][0]>=pr[i+8][0] && tc[j][0]<=pr[i+8][2] && tc[j][1]>=pr[i+8][1] && tc[j][1]<=pr[i+8][3]) ++o[8];
        if (tc[j][0]>=pr[i+9][0] && tc[j][0]<=pr[i+9][2] && tc[j][1]>=pr[i+9][1] && tc[j][1]<=pr[i+9][3]) ++o[9];
           }
 
    }    
    printf("%i\n",o[0]);
    if (i<pob[1])
    {
    printf("%i\n%i\n%i\n%i\n%i\n%i\n%i\n%i\n%i\n",o[1],o[2],o[3],o[4],o[5],o[6],o[7],o[8],o[9]);
    i=i+9;
    }
}
return(0);
}
 
 

Всего записей: 69 | Зарегистр. 26-09-2001 | Отправлено: 12:32 16-11-2006 | Исправлено: Drol, 12:45 16-11-2006
vertex4

Moderator
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Drol
При такой постановке вопроса можно написать прогу с использованием MPI библиотеки, под многопроцессорные системы. Представляешь, насколько быстрее будет вычисление на кластере?

----------
В любой инструкции пропущено самое важное - что делать, если это устройство или программа не работают

Всего записей: 10393 | Зарегистр. 29-01-2006 | Отправлено: 12:55 16-11-2006
Drol



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
vertex4
Drol  
При такой постановке вопроса можно написать прогу с использованием MPI библиотеки, под многопроцессорные системы. Представляешь, насколько быстрее будет вычисление на кластере?

Мне сказали, что задача решаемая и действительно она решаеться на простом P-4/1.8Ghz.

Всего записей: 69 | Зарегистр. 26-09-2001 | Отправлено: 13:01 16-11-2006 | Исправлено: Drol, 13:03 16-11-2006
Mickey_from_nsk

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Drol
Немного странно видеть в коде, который должен быть оптимизирован по самое нехочу (даже переменную цикла в регистры засовываешь) функцию scanf. Не самая быстрая функция, хочу заметить.  

Цитата:
for (register int i=0; i<pob; ++i)  
{  
    scanf("%i%i%i%i",&p[0],&p[1],&p[2],&p[3]);  
    pr[i]=0;  
 

Огромные scanf во втором случае выглядят еще хуже. Да и вообще там ты сильно перемудрил.
 
Однако, ты уже сам понял, что ввод - дело гиблое, его надо ускорять.
 
В этом случае просто необходимо использовать "сырой" ввод через функцию read с явным прямым заполнением массивов (естественно, данные должны быть предварительно подготовлены). Делать это надо до этих циклов.
 
Если бы ты удосужился прогнать программу в профайлере, то, видимо, с удивлением обнаружил бы , что ~80% времени уходит на обработку ввода (может даже и больше). Так что считай, что ты там оптимизировать должен.
 
Ну и в качестве мысли вдогонку. А не стоило бы отсортировать массив точек?
Ведь еще фиг знает кем доказано, что бинарный поиск по сортированному массиву существенно быстрее чем линейный поиск по несортированному.

Всего записей: 636 | Зарегистр. 21-10-2002 | Отправлено: 13:02 16-11-2006
Drol



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Mickey_from_nsk
 
Проверяли scanf и printf работают быстрее чем, cin и cout.
скорее всего больше уходит время в двойном цикле, оба цикла общее получаеться 400000000 оборотов, Значит cтолько долженj выполнить команды внутри этих циклов. Надо найти такой алгорит, который имел меньше операции и быстро выполнялись команды.
 
for (i=0; i<pob[0]; ++i)  
{   o[0]=0;o[1]=0;o[2]=0;o[3]=0;o[4]=0;o[5]=0;o[6]=0;o[7]=0;o[8]=0;o[9]=0;  
    for (j=0;j<tob[0];++j)  
 
Эту программу примером показал. Может другие ее решат подругому. Я не так силен в С++. Спросил в форуме, может кто может по иному пути решить задачу.

Всего записей: 69 | Зарегистр. 26-09-2001 | Отправлено: 13:28 16-11-2006 | Исправлено: Drol, 13:30 16-11-2006
Mickey_from_nsk

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Drol

Цитата:
Проверяли scanf и printf работают быстрее чем, cin и cout.  
 

Дык никто и не говорит, что медленнее. Я говорил про более "сырой" ввод вывод - read и write. Причем одним блоком. У тебя же длиннющщий массив, нафиг его поэлементно заполнять, если можно сразу весь?
А про время работы циклов - это однозначно понятно, что там все просаживается. Только вот вопрос "на чем это все садится"? Я более чем уверен - на scanf. Вынеси его за цикл и замени на read.

Всего записей: 636 | Зарегистр. 21-10-2002 | Отправлено: 13:42 16-11-2006
Drol



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Mickey_from_nsk

Цитата:
У тебя же длиннющщий массив, нафиг его поэлементно заполнять, если можно сразу весь?  

А как можно сразу весь?

Всего записей: 69 | Зарегистр. 26-09-2001 | Отправлено: 14:51 16-11-2006 | Исправлено: Drol, 14:51 16-11-2006
Qraizer



Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Блин, ну будет scanf() он заменён на read(), что с того? Исходный файл тектсовый? Текстовый. Значит ввод должен быть форматированным? Форматированным. read() какой ввод делает? Правильно - неформатированный. Следовательно что после read() придётся сделать? sscanf()? Где логика? Тут у вас полный перебор, а вы за какой-то scanf() уцепились.
Не приходила в голову мысль отсортировать прямоугольники по координатам углов? Это четыре массива получится. Затем для каждой точки в каждом массиве искать, какие прямоугольники включают её в себя. Это четыре бинарных поиска. Останется только найти пересечение четырёх множеств.

Всего записей: 613 | Зарегистр. 08-08-2006 | Отправлено: 15:04 16-11-2006 | Исправлено: Qraizer, 18:17 16-11-2006
AlexeyTyabin

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Задание 1. . Вычислить указанные  характеристики последовательности(4343, 9131, 33, 3313, 646, 3223, 1313, 0) , заканчивающейся нулем (0) и вводимой с клавиатуры (без использования массивов и промежуточных файлов для хранения всей последовательности), учитывая, что элементы последовательности могут быть введены только один раз.  
В программе обязательно применение функций с передаваемыми параметрами. Рекомендуется использовать операции целочисленной арифметики. Если в после¬дова¬тельности отсутствует искомый элемент, то об этом следует вывести сообщение. Размер числа ограничен использованным в программе типом. Программа должна обрабатывать все возможные нестандартные случаи (например: пустую последовательность). Последний элемент последовательности 0 – не обрабатывается.  
 
2.Найти такие элементы (а также их сумму), которые состоят из двух равных частей и имеют в своем составе цифру 3.

Всего записей: 6 | Зарегистр. 04-11-2006 | Отправлено: 18:28 16-11-2006
HRyk



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Rain87, привет! Чем занимаешься? Настроение бодрое? Rain87, будет время, опиши, пожалуйста, пошагово размен "17" купюрами в 11,1,8  
while(i<nnoms)  
  {  
    for(j=0;j<m;j++)  
      if(dyn[j])  
    if(j+noms[i]<=m)  
      if(!dyn[j+noms[i]]||len[j]+1<len[j+noms[i]])  
      {  
        dyn[j+noms[i]]=1;  
        how[j+noms[i]]=j;  
        nnom[j+noms[i]]=i;  
        len[j+noms[i]]=len[j]+1;  
      }  
    i++;  
  }  
алгоритм нифига не улавливаю (понимаю, что выгляжу глупо) въехал только в то, что мы здесь пробегаем все номера номиналов и все натуральные числа до введенной суммы. Rain87, буду очччень признателен!!!
 
Добавлено:
Друзья, кто сейчас без  дела помогите разобраться с задачей: "Построить первые n натуральных чисел, делителями которых являются только числа 2,3,5" Я вставлял ветвления на деление натурального числа на 6, 15, 9 , но потом понял, что это бесполезно, т. к. комбинации 2-ки, 3-ки и 5-ки могут быть вообще любые. Что делать!!!

Всего записей: 162 | Зарегистр. 04-11-2006 | Отправлено: 19:35 16-11-2006
rain87



Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Qraizer
если можно, поподробнее... не пойму, как это реализовать
 
мой вариант:
засунуть Х координаты начал и концов всех прямоугольников в один массив, У - в другой массив (при этом запомнить, какая координата является началом/концом какого прямоугольника)
 
отсортировать каждый из массивов (quicksort, за n*log n)
 
для каждого из отрезков x[i]..x[i+1], y[i]..y[i+1] определить, какие прямоугольники покрывают эту область (линейный просмотр)
 
затем для каждой точки - двоичным поиском определить к какой области по Х и по У она относится, и те номера прямоугольников, которые будут и в том, и в том отрезках - содержат эту точку
 
по времени она пройдёт 100%, узкое место - память для хранения, какие прямоугольники покрывают какую область в худшем случае понадобится... много памяти
 
но если не будет специально подобранных тестов, то рандом вряд ли такой сгенерит
 
если же не прокатит по памяти... тогда можно будет не формировать,  какие прямоугольники покрывают эту область - каждый раз делать это для каждой точки. т.е. бинарно определить, где точка - и либо с конца, либо с начала (откуда ближе) подбираться к этому отрезку, попутно формируя список прямоугольников
 
в худшем случае - не прокатит по времени
 
а 100% решения что-то не вижу навскидку
 
Добавлено:
HRyk
ну раз сишный дебагер не устраивает, хорошо. порабатаю им
Подробнее...

Всего записей: 1744 | Зарегистр. 21-06-2006 | Отправлено: 19:55 16-11-2006
Ice2dk

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Нужно написать консольную программу которая выводит      ******
                                                                                         ***
                                                                                          **
                                                                                           *
                                                                                           *
                                                                                          **
                                                                                         ***
                                                                                      ******
 
типа из звёздочек песочные часы!! знаю что очень легко но не владею почти языком! помогите плизззз

Всего записей: 3 | Зарегистр. 16-11-2006 | Отправлено: 20:55 16-11-2006 | Исправлено: Ice2dk, 20:55 16-11-2006
rain87



Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Ice2dk
такое подойдёт?
Код:
#include <stdio.h>
 
void main()
{
  printf("*******\n\
 *****\n\
  ***\n\
   *\n\
  ***\n\
 *****\n\
*******\n");
}

Всего записей: 1744 | Зарегистр. 21-06-2006 | Отправлено: 21:29 16-11-2006 | Исправлено: rain87, 21:30 16-11-2006
Ice2dk

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
не конешно спасибо но чреез принт и cout не подходит нада церез цикли фор

Всего записей: 3 | Зарегистр. 16-11-2006 | Отправлено: 21:36 16-11-2006
vertex4

Moderator
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
#include <stdio.h>  
 
void main()  
{ int k=5;  
While (k!=0)
{for (int i=0;i<k;i++)
  printf("*" );
printf("/n");
k--;
}
While (k!=5)
{for (int i=0;i<k;i++)
  printf("*" );
printf("/n");
k++;
}
}
 
C++ нету, так что сам компиль, ошибки ищи
 
Добавлено:

Цитата:
While (k!=5)

Ой, тут боюсь запутаться.
Но всё настраивается, любой разме "часов".

----------
В любой инструкции пропущено самое важное - что делать, если это устройство или программа не работают

Всего записей: 10393 | Зарегистр. 29-01-2006 | Отправлено: 21:45 16-11-2006
Ice2dk

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
vertex4

 
Большое спасибо тебе всё работает!

Всего записей: 3 | Зарегистр. 16-11-2006 | Отправлено: 22:01 16-11-2006
akaGM

Platinum Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:

Код:
While (k!=5)

Ой, тут боюсь запутаться.  

 

Цитата:
Большое спасибо тебе всё работает!

 
гы
шутники...

Всего записей: 24037 | Зарегистр. 06-12-2002 | Отправлено: 22:13 16-11-2006
Открыть новую тему     Написать ответ в эту тему

Страницы: 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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Задачи по C/С++


Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.B0ard
© Ru.B0ard 2000-2024

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

Рейтинг.ru