Задачки для разминки. (Простенькие такие...)

[Olej]

№3 : Всем задачам задача
Как можно (и нужно!) в коде C представлять комплексные числа?

Задача крайне актуальная, потому как комплексные числа - естественная и наилучшая форма выражения координат в 2D графике. А кроме того, комплекмсная математика - это все, без исключения, расчёты в электротехнике, радиотехнике, цифровых фильтрах и мн. др. областях.

Как выразить комплексными значениями координаты 2-х точек на 2D плоскости ... и найти расстояние между ними, как простейшее действие.

[Olej]

№4 : Препроцессор...
Какой будет результат выполнения:

Код: Выделить всё

#define SIZE sizeof( int ) * 8
const int size = SIZE;
//...
int x = 64;
printf( "%d\n", x / SIZE );
printf( "%d\n", x / size );

[Olej]

№5 :
Палиндромом называется строка, которая читается одинаково слева-направо и справа-налево, например «12321».
При анализе на палиндром строк, символы пробелов и знаков препинания исключаются из рассмотрения (пропускаются), вот примерно так:

Код: Выделить всё

$ ./palindrom
Введите тестируемую строку : строка
строка не палиндром
Введите тестируемую строку : Я иду с мечем судия
строка палиндром
Введите тестируемую строку : Аргентина манит негра
строка палиндром
Введите тестируемую строку : А роза упала на лапу Азора
строка палиндром
Введите тестируемую строку : На в лоб, болван
строка палиндром
Введите тестируемую строку : ^C

Напишите такую программу palindrom, которая анализирует вводимые строки являются ли они палиндромами (на C или C++ ... да, собственно, на любом языке) .

[Olej]

№6 : Разбейте произвольную русскоязычную строку на слова, и выведите слова в обратном первоначальному порядке.


№7 : С клавиатуры вводится натуральное число, к десятичной записи которого добавляется в начало и в конец цифра 1 (например: 372->13721). В итоге определить, простое ли это получившееся число?


№8 :Напишите программу нахождения всех натуральных чисел, не превосходящих N и делящихся на каждую из своих цифр (в виду простоты задачи, дополнительное пожелание - запишите код максимально коротко).

[Olej]

Поскольку тему назвали "Задачки для разминки", но ... никто разминаться не собирается - выкину я сюда варианты решений задачек, начиная с последней:

№8 :Напишите программу нахождения всех натуральных чисел, не превосходящих N и делящихся на каждую из своих цифр (в виду простоты задачи, дополнительное пожелание - запишите код максимально коротко).

Код: Выделить всё

#include <stdio.h>

int main() {
   while( 1 ) {
      unsigned long lim, i;
      printf( "limit: ");
      if( scanf( "%lu", &lim ) != 1 ) break;
      printf( "%lu => ", lim );
      for( i = 1; i <= lim; i++ ) {
         unsigned long j = lim;
         do {
            if( !( j % 10 ) ) continue;
            if( ( i % ( j % 10 ) ) ) break;
         } while( j /= 10 );
         if( 0 == j ) printf( "%lu ", i );
      }
      printf( "\n" );
   }
   printf( "\n" );
   return 0;
}

Код: Выделить всё

$ ./divdig
limit: 357
357 => 105 210 315
limit: 579
579 => 315
limit: 2357
2357 => 210 420 630 840 1050 1260 1470 1680 1890 2100 2310
limit: 567
567 => 210 420
limit: 5670
5670 => 210 420 630 840 1050 1260 1470 1680 1890 2100 2310 2520 2730 2940 3150 3360 3570 3780 3990 4200 4410 4620 4830 5040 5250 5460 5670
limit: ^D

[bormant]

Olej,
ох, недоразмялись...

делящихся на каждую из своих цифр

Если в числе есть одна или несколько цифр "0", то число не подходит? Или считаем, что на "0" делится любое число?

Код: Выделить всё

limit: 357
357 => 105 210 315
limit: 579
579 => 315

Куда пропали 105 и 210?
Где же 1, 11, 111?

PS.
Limit: 357
1 2 3 4 5 6 7 8 9 10 11 12 15 20 22 24 30 33 36 40 44 48 50 55 60 66 70 77 80 88 90 99 100 101 102 104 105 110 111 112 115 120 122 124 126 128 132 135 140 144 150 155 162 168 175 184 200 202 204 208 210 212 216 220 222 224 240 244 248 250 264 280 288 300 303 306 312 315 324 330 333 336

Код: Выделить всё

var n, m: LongInt;
begin
  Write('Limit: '); ReadLn(n);
  for n:=1 to n do begin
    m:=n; while (m<>0) and ((m mod 10=0) or (n mod (m mod 10)=0)) do m:=m div 10;
    if m=0 then Write(' ',n);
  end; WriteLn;
end.

PPS. Если на цифру "0" делить нельзя, то
Limit: 357
1 2 3 4 5 6 7 8 9 11 12 15 22 24 33 36 44 48 55 66 77 88 99 111 112 115 122 124 126 128 132 135 144 155 162 168 175 184 212 216 222 224 244 248 264 288 312 315 324 333 336

Код: Выделить всё

var n, m: LongInt;
begin
  Write('Limit: '); ReadLn(n);
  for n:=1 to n do begin
    m:=n; while (m<>0) and (m mod 10<>0) and (n mod (m mod 10)=0) do m:=m div 10;
    if m=0 then Write(' ',n);
  end; WriteLn;
end.

[Olej]

Если в числе есть одна или несколько цифр "0", то число не подходит? Или считаем, что на "0" делится любое число?

Естественно, на 0 делить не можно, поэтому проверку на 0 просто обходим.

Код: Выделить всё

limit: 579
579 => 315

Куда пропали 105 и 210?

105 и 210 никуда не пропали - они просто не делятся на 9

Где же 1, 11, 111?

Код: Выделить всё

$ ./divdig
limit: 11
11 => 1 2 3 4 5 6 7 8 9 10 11
limit: 111
111 => 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
limit: ^C

PS.
Limit: 357
1 2 3 4 5 6 7 8 9 10 11 12 15 20 22 24 30 33 36 40 44 48 50 55 60 66 70 77 80 88 90 99 100 101 102 104 105 110 111 112 115 120 122 124 126 128 132 135 140 144 150 155 162 168 175 184 200 202 204 208 210 212 216 220 222 224 240 244 248 250 264 280 288 300 303 306 312 315 324 330 333 336

Я же предлагал найти не те числа, которые делятся на какую-то з своих цифр (ИЛИ), а которые делятся на все свои цифры (И).
7 в этом ряду не делится на 3, 9 - не делится на 5 ... а 11 - откровенно не делися ни на что

[Olej]

Такая вот развлекуха ... снизу в верх:

№7 : С клавиатуры вводится натуральное число, к десятичной записи которого добавляется в начало и в конец цифра 1 (например: 372->13721). В итоге определить, простое ли это получившееся число?

Код: Выделить всё

int is_simple( unsigned long n ) {
   unsigned long i;
   for( i = 3; i * i <= n; i += 2 )
      if( !( n % i ) ) return 0;
   return 1;
}

int main() {
   while( 1 ) {
      char buf[ 80 ] = "1";
      printf( "число: ");
      if( !fgets( buf + 1, sizeof( buf ) - 1, stdin ) ) break;
      *strchr( buf, '\n' ) = '1';
      printf( "число: %s %s\n", buf,
              is_simple( atol( buf ) ) != 0 ? "простое" : "не простое" );
   }
   printf( "\n" );
   return 0;
}

Здесь есть откровенный обман ... с приписыванием 1 спереди и сзади

Код: Выделить всё

$ ./simple1
число: 15
число: 1151 простое
число: 23
число: 1231 простое
число: 29
число: 1291 простое
число: 30
число: 1301 простое
число: 31
число: 1311 не простое
число: 32
число: 1321 простое
число: 33
число: 1331 не простое
число: 38
число: 1381 простое
число: 372
число: 13721 простое
число: 373
число: 13731 не простое
число: ^D

[bormant]

Olej
вы решили не ту задачу, условие которой привели.
В той, что привели, нужно найти такие числа, не превосходящие N, которые (найденные числа) делятся на все свои (найденного числа) цифры.
В той, что решали вы, найдены такие числа, не превосходящие N, которые делятся на все цифры числа N.
Почувствуйте разницу.
Решения исходных задач на C:
всё делится на "0":

Код: Выделить всё

#include <stdio.h>
void main() {
    unsigned long lim;
    printf( "limit: "); scanf( "%lu", &lim );
    for( unsigned long i=1; i<=lim; ++i ) {
        unsigned long j=i;
        while( j && (!(j%10) || !(i%(j%10))) ) j/=10;
        if( !j ) printf( " %lu", i );
    }
    printf( "\n" );
}

на "0" делить нельзя:

Код: Выделить всё

#include <stdio.h>
void main() {
    unsigned long lim;
    printf( "limit: "); scanf( "%lu", &lim );
    for( unsigned long i=1; i<=lim; ++i ) {
        unsigned long j=i;
        while( j && j%10 && !(i%(j%10)) ) j/=10;
        if( !j ) printf( " %lu", i );
    }
    printf( "\n" );
}

[Olej]

вы решили не ту задачу, условие которой привели.
В той, что привели, нужно найти такие числа, не превосходящие N, которые (найденные числа) делятся на все свои (найденного числа) цифры.
В той, что решали вы, найдены такие числа, не превосходящие N, которые делятся на все цифры числа N.
Почувствуйте разницу.

Значит я просто неправильно сформулировал цель задачи.
Исправлюсь...
В такой (новой, вашей, уточнённой) формулировке задача, конечно, совсем другая ... но она становится менее интересной.

[bormant]

В такой (новой, вашей, уточнённой) формулировке задача, конечно, совсем другая ... но она становится менее интересной.

Разница только в одной строке
исходная:

Код: Выделить всё

unsigned long j=i;

решенная вами:

Код: Выделить всё

unsigned long j=lim;

[bormant]

Olej
задача №8 в вашей трактовке решается намного проще и эффективнее, если сначала найти произведение уникальных цифр числа N, а затем сгенерировать искомые числа, например, так:

Код: Выделить всё

#include <stdio.h>
void main() {
    long lim, k=1;
    printf( "limit: " ); scanf( "%ld", &lim );
    for( long i=lim; i; i/=10 )
        if( i%10 && k%(i%10) ) k*=i%10;
    for( long i=lim/k*k; i>=k; i-=k )
        printf( " %ld", i );
    printf( "\n" );
}

[Olej]

задача №8 в вашей трактовке решается намного проще и эффективнее, если сначала найти произведение уникальных цифр числа N, а затем сгенерировать искомые числа, например,

Не совсем так, это если нет повторов цифр:

Код: Выделить всё

 $ ./divdig
limit: 33
33 => 3 6 9 12 15 18 21 24 27 30 33
limit: ^C

21 - делится на 3, но не обязано делиться на 9.

Эффективнее можно сделать, если цифры исходные сразу выделить ... в массив, или ещё лучше в множество set если это C++.
Но про эффективность задача не стояла.

P.S. Это не мои задачи, и не мои ... трактовки. Все эти задачи мне "подбросили" в разное время при разных обстоятельствах. То, что показалось занятным - осталось.
Я могу таких занятных задачек ... до сотни накидать

[bormant]

Olej
В числе 33 только одна цифра -- 3. Если нужно учитывать каждую цифру по количеству вхождений, то всё еще проще, достаточно убрать специально добавленное условие, исключавшее дублирование (&& k%(i%10)).

Код: Выделить всё

#include <stdio.h>
void main() {
    long lim, k=1;
    printf( "limit: " ); scanf( "%ld", &lim );
    for( long i=lim; i; i/=10 )
        if( i%10 ) k*=i%10;
    for( long i=lim/k*k; i>=k; i-=k )
        printf( " %ld", i );
    printf( "\n" );
}

[Olej]

Поехали дальше ... от конца к началу?

№6 : Разбейте произвольную русскоязычную строку на слова, и выведите слова в обратном первоначальному порядке.

Код: Выделить всё

inline void c2w( char *c, wchar_t *w ) {
   int n = -1;
   setlocale( LC_ALL, "" );  // только после этого работают преобразования!
   while( n != 0 )
      c += ( n = mbtowc( w++, c, MB_CUR_MAX ) );
}

void revers( wchar_t *w ) {
   wchar_t *sec, wb[ 40 ];
   if( NULL == ( sec = wcschr( w, L' ' ) ) ) return;
   wcsncpy( wb, w, sec - w )[ sec - w ] = L'\0';
   while( L' ' == *sec ) sec++;
   revers( sec );
   wcscat( wcscat( wmemmove( w, sec, wcslen( sec ) + 1 ), L" " ), wb );
}

#define LENGTH 160
char    buf  [ LENGTH ] = "тестовая русскоязычная  строка  в UTF-8 с прямым порядком слов ";
wchar_t wbuf [ LENGTH ];

void test05( void ) {
   c2w( buf, wbuf );
   while( L' ' == wbuf[ wcslen( wbuf ) - 1 ] )
      wbuf[ wcslen( wbuf ) - 1 ] = L'\0';
   printf( "устранение завершающих пробелов: '%ls'\n", wbuf );
   revers( wbuf );
   printf( "реверсирование слов: '%ls'\n", wbuf );
   revers( wbuf );
   printf( "реверсирование слов: '%ls'\n", wbuf );
}

Этот код выдернут из совсем другого контекста, поэтому его не обсуждаем...
А сформулирована задача и показан пример вот для чего:
- разобрать содержимое любой русскязычной строки (или китайской) у вас не получится без установления локали ... setlocale( LC_ALL, "" ) или подобным способом;
- разобрать содержимое русскязычной строки не получится в формате char [] - нужно преобразовывать к широким символам wchar_t []
- преобразования делаются группой функция вида mb*() (mbtowc() и др. - пеобразования мультибайтных символов в широкие);
- для работы с широкими символами используется такой же набор строчных функций как str*(), только начинаться они будут с префикса wcs*();

Код: Выделить всё

$ ./unicode
устранение завершающих пробелов: 'тестовая русскоязычная  строка  в UTF-8 с прямым порядком слов'
реверсирование слов: 'слов порядком прямым с UTF-8 в строка русскоязычная тестовая'
реверсирование слов: 'тестовая русскоязычная строка в UTF-8 с прямым порядком слов'

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

[Olej]

№5 :
Палиндромом называется строка, которая читается одинаково слева-направо и справа-налево, например «12321».
При анализе на палиндром строк, символы пробелов и знаков препинания исключаются из рассмотрения (пропускаются), вот примерно так:

Язык C++ (это не принципиально важно).

Код: Выделить всё

#include <iostream>
#include <locale>
using namespace std;

int main( int argc, char *argv[] ) {
   bool debug = argc > 1 && "debug" == string( argv[ 1 ] );
   locale::global( locale( "" ) );
   while( 1 ) {
      wcout << L"Введите тестируемую строку : ";
      wstring w( L"\n" );
      getline( wcin, w );
      if( debug ) wcout << L"[" << w.size() << L"]: " << w << endl;
      bool poli;
      wchar_t *s = (wchar_t*)w.c_str(),
              *pb = s, *pe = pb + wcslen( s ) - 1;
      do {
         while( *pb == ' ' ) pb++;
         while( *pe == ' ' ) pe--;
         poli = towlower( *pb ) == towlower( *pe );
         if( debug ) wcout << *pb << " ? " << *pe << " = " << ( poli ? "+" : "-" )<< endl;
      } while( poli && ++pb <= --pe );
      wcout << L"строка " << ( poli ? L"" : L"не " ) << L"палиндром" << endl;
   }
}

Код: Выделить всё

$ ./palindrom
Введите тестируемую строку : строка
строка не палиндром
Введите тестируемую строку : Я иду с мечем судия
строка палиндром
Введите тестируемую строку : Аргентина манит негра
строка палиндром
Введите тестируемую строку : А роза упала на лапу Азора
строка палиндром
Введите тестируемую строку : На в лоб, болван
строка палиндром
Введите тестируемую строку : ^C

Вот здесь есть вопрос к знатокам...
Почему
- если в программе только где-то выполняется вывод в cout ... не важно что, что-то типа:

Код: Выделить всё

int x = 2;
cout << x << endl;

- любой последующий вывод, использующий wcout:
wcout << L"строка " << endl;
- идёт с ошибками (т.е. аообще не идёт, производит какой-то 16-ричный вывод).
Чем такое может объясняться?
Каким-то образом разрушаютя флаги состояния потока вывода

[Olej]

Чем такое может объясняться?
Каким-то образом разрушаютя флаги состояния потока вывода

Вот примерно таким образом... делаем 2 приложения:

Код: Выделить всё

int main() {
   locale::global( locale( "" ) );
   wcout << L"строка " << endl;
   return 0;
}

Код: Выделить всё

int main() {
   locale::global( locale( "" ) );
   cout << "строка" << endl;
   wcout << L"строка " << endl;
   return 0;
}

И смотрим что из этого получилось:

Код: Выделить всё

olej@nvidia ~/2016_WORK/in.WORK/out $ ./out1
строка
olej@nvidia ~/2016_WORK/in.WORK/out $ ./out2
строка
AB@>:0

Почему?

[Bizdelnick]

Знатоком C++ я б себя не назвал, но документация рулит:

A program should not mix output operations on wcout with output operations on cout (or with other narrow-oriented output operations on stdout): Once an output operation has been performed on either, the standard output stream acquires an orientation (either narrow or wide) that can only be safely changed by calling freopen on stdout.

Так что, в общем-то, C++ тут не виноватый.

[Olej]

Знатоком C++ я б себя не назвал, но документация рулит:

A program should not mix output operations on wcout with output operations on cout (or with other narrow-oriented output operations on stdout): Once an output operation has been performed on either, the standard output stream acquires an orientation (either narrow or wide) that can only be safely changed by calling freopen on stdout.

Так что, в общем-то, C++ тут не виноватый.

Дело не в "виноватый"/"не виноватый".
Но эта особенность имеет отношение именно к C++, потому как в C printf() может однаково хорошо, вперемешку работать с выводом как широких символов, так и char.
А вот упоминание вскользь freopen() - это интересно, нужно будет проверить.

[Bizdelnick]

Ну так printf() сам wchar преобразует в char. А вот если сделать fputs() в stdout, то потом fputws() туда уже не работает (и наоборот).

[Olej]

A program should not mix output operations on wcout with output operations on cout (or with other narrow-oriented output operations on stdout): Once an output operation has been performed on either, the standard output stream acquires an orientation (either narrow or wide) that can only be safely changed by calling freopen on stdout.

Только непонятно как можно выполнить freopen() для стандартного потока вывода (когда это не поток переназначаемый в файл):

Код: Выделить всё

FILE *freopen(const char *path, const char *mode, FILE *stream);

Всё понятно кроме path.
Может кто сможет что придумать?

[Bizdelnick]

"/dev/stdout"?

[Olej]

"/dev/stdout"?

Ну что ж ... это, в принципе, работает (грубовато как-то выглядит, но работает):

Код: Выделить всё

using namespace std;

int main() {
   locale::global( locale( "" ) );
   cout << "строка1" << endl;
   stdout = freopen( "/dev/stdout", "w", stdout );
   wcout << L"строка2" << endl;
   stdout = freopen( "/dev/stdout", "w", stdout );
   cout << "строка3" << endl;
   stdout = freopen( "/dev/stdout", "w", stdout );
   wcout << L"строка4" << endl;
   return 0;
}

Код: Выделить всё

olej@nvidia ~/2016_WORK/in.WORK/out $ make
g++ -Wall -std=c++11 -O3     out3.cc   -o out3
olej@nvidia ~/2016_WORK/in.WORK/out $ ./out3
строка1
строка2
строка3
строка4

[Olej]

"/dev/stdout"?

А как это делать ... тем несчастным, которые привыкли писать на C++ в Windows?
В принципе, всегда и повсеместно утврждалось (Страутруп и др.), что C++ более переносим, чем C. да так же оно ощущается и из реальной практики написания кода. Но в данном случае C++ не менее архитектурно привязан, чем и C.

[Bizdelnick]

И опять документация рулит:

If filename is a null pointer, the function attempts to change the mode of the stream. Although a particular library implementation is allowed to restrict the changes permitted, and under which circumstances.

[Olej]

И опять документация рулит:

If filename is a null pointer, the function attempts to change the mode of the stream. Although a particular library implementation is allowed to restrict the changes permitted, and under which circumstances.

Это уже теплее :

Код: Выделить всё

int main() {
   locale::global( locale( "" ) );
   cout << "строка1" << endl;
   stdout = freopen( NULL, "w", stdout );
   wcout << L"строка2" << endl;
   stdout = freopen( NULL, "w", stdout );
   cout << "строка3" << endl;
   stdout = freopen( NULL, "w", stdout );
   wcout << L"строка4" << endl;
   return 0;
}

Код: Выделить всё

olej@nvidia ~/2016_WORK/in.WORK/out $ ./out4
строка1
строка2
строка3
строка4

Кстати ... вот небольшой архивчик, где 10 короких образцов "cout vs wcout" на языках C и C++ - может кому пригодится для памятки.

[Olej]

"/dev/stdout"?

А как это делать ... тем несчастным, которые привыкли писать на C++ в Windows?

Удивительное дело, но, хоть это и нарушение стандарта, но в Windows компиляторах-средах-библиотеках запись вперемежку в cout и wcout не порождает никаких проблем .

Но ещё удивительнее то, что от способ как это происходит, зависит от используемого компилятора-библиотек (это выше моего понимания).
Вот картинка (прикриплена) в VisualStudio 2010.
Как легко видеть, этот Studio легко сожрал:

Код: Выделить всё

int main() {
   setlocale( LC_ALL, "rus" );
   cout << "строка1" << endl;
   wcout << L"строка2" << endl;
   cout << "строка3" << endl;
   wcout << L"строка4" << endl;
   return 0;
}

А каринку для Code::Blocks я показывал в соответствующей теме:

Это MinGW компилятор (GCC)
Тому вообще понравилось:

Код: Выделить всё

int main() {
   setlocale( LC_ALL, "rus" );
   cout << "строка1" << endl;
   wcout << "строка2" << endl;
   cout << "строка3" << endl;
   wcout << "строка4" << endl;
   return 0;
}

А на строчные константы в виде L"строка2" - он вообще нещадно ругается.

Неисповедимы пути Widows!

[Olej]

№4 : Препроцессор...
Какой будет результат выполнения:

Код: Выделить всё

#define SIZE sizeof( int ) * 8
const int size = SIZE;
//...
int x = 64;
printf( "%d\n", x / SIZE );
printf( "%d\n", x / size );

Ну, это совсем просто, чтобы коментировать, Здесь будет:

Код: Выделить всё

128
2

Но в такую засаду можно ненароком попасть в реальном большом коде ... и тогда становися не до смеха.

[Olej]

№3 : Всем задачам задача
Как можно (и нужно!) в коде C представлять комплексные числа?
...
Как выразить комплексными значениями координаты 2-х точек на 2D плоскости ... и найти расстояние между ними, как простейшее действие.

А это задача уж совсем провокционная ... потому что в ответ городят что-то типа

Код: Выделить всё

struct point { double x, y; };

Или ещё хуже того:

Код: Выделить всё

struct point { double x, y; };

А в C++ и так (я сам, по удобству, по ситуации - в некоторых случаях такое могу исользовать):

Код: Выделить всё

class point : protected pair<double, double> {};

Но только:
- естественной формой математического изображения 2D точки являются компле́ксные значения (вот как на картинке) ...
- и в C их действительно не было ... но только до 1999г. (C99 ... точнее даже C89, но полноценная библитека операций только с C99)
- и все комплексные операции были включены повсеместно используемую нами всеми (от даты изобретения C) библиотеку libm.so
- и об этом следует напоминать

И тогда расстояние между двумя точками или площадь треугольника, построенного на двух векторах (Z1 и Z10 на картинке) выражается нативными компле́ксными операциями:

Код: Выделить всё

double complex z1 = 1. + 1. * I,
                        z10 = sqrt( 2. ) - I;
double d = cabs( z1 - z10 ),
           s = 0.5 * cabs( z1 ) * cabs( z10 ) * fabs( sin( carg( z1 ) - carg( z10 ) ) );
printf( "расстояние = %f , площадь = %d\n", d, s );

[Olej]

№2 : В обработке временных рядов, цифровой обработке сигналов и для других целей часто вычисляется среднее и дисперсия (и далее среднеквадратичное отклонение) числовой последовательности X[ i ]: mean = 1 / N * ∑( X[ i ] ), disp = 1 / N * ∑( ( X[ i ] - mean )² ). Но прямое вычисление характеристик по математическим формулам требует 2-х проходов: сначала вычисление среднего, а затем уже — дисперсии. Самое худшее при этом, что нужно хранить в памяти задачи всю последовательность чисел, что при больших N неприемлемо. Напишите программу для вычисления среднего и дисперсии (массива для примера) в 1 проход, в потоке поступления входных чисел, без их хранения.

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

Если раскрыть выражение (квадрат разности) для дисперсии и произвести дальнейшие упрощения, то можно прийти к выражению: disp = 1 / N * ∑( X[ i ]² ) - mean². Теперь мы можем накапливать сумму квадратов последовательности чисел в потоке, а вычисление характеристик отложить на завершение. Вот вариант реализации:

Код: Выделить всё

#include <stdio.h>
#include <unistd.h>

int main() {
   int n = 0;
   double s1 = 0.0, s2 = 0.0;
   if( isatty( STDIN_FILENO ) != 0 &&   // только терминал
       isatty( STDOUT_FILENO ) != 0 ) {
         printf( "вводите числа (^D завершение): " );
         fflush( stdout );
   }
   while( 1 ) {
      float d;
      if( EOF == scanf( "%f", &d ) )
         break;
      n++;
      s1 += d;
      s2 += d * d;
   }
   s1 /= n;
   s2 = s2 / n - s1 * s1;
   if( isatty( STDOUT_FILENO ) != 0 )
      printf( "введено чисел %d, среднее=%f, дисперсия=%f\n", n, s1, s2 );
   else
      printf( "%f %f\n", s1, s2 );
   return 0;
}

Проверяем:

Код: Выделить всё

$ ./sko
вводите числа (^D завершение): 3
4
5
введено чисел 3, среднее=4.000000, дисперсия=0.666667
$ ./sko <sko_test.dat
введено чисел 3, среднее=4.000000, дисперсия=0.666667
$ ./sko <sko_test.dat >sko.out
$ cat sko.out
4.000000 0.666667

Задачка - игрушечная. А вот способ вычисления дисперсии / мощности / СКО числового потока без знаия среднего (постоянной составляющей) - оченьдаже настоящий.
Кто хоть как-то планирует иметь дело с анализом или оработкой сигналов - обратите внимание.