среда, 2 июня 2010 г.

найти родственников

Задано конечное множество имен жителей некоего города,
причем для каждого из жителей перечислены имена его детей.
Жители X и Y называются родственниками ,если

a) либо X - ребенок Y
b) либо Y - ребенок X
c) либо существует некий Z такой, что X - родственник Z, а Z - родственник Y.

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



Задача, как по мне, выше среднего уровня.

Первая проблема которая перед нами стоит - это как задать начальные данные.
Я долго думал на эту тему и пришел к выводу, что пользователю проще работать
с именами, чем с индексами соотв. имени. Поэтому я не пошел стандартным путём
(  а это задание вектора имен, потом задание вектора векоторов + вектор булевых переменных для раскраски... - муть зеленая)

Я использовал наборы из STL, т.е std::set

Для описания связи я использовал std::pair

Задав таким образом пары мы перезходим к следующей проблеме - нужно получить список уникальных имен, т.е. получить набор всех жителей. С этим отлично справился контейнер std::set.

Теперь нам нужно оценить каждого с каждым на предмет родства, это делать удобнее с std:vector - поэтому мы перегоняем данные из set в vector

Ну и самое главное - определение родства. Используем рекурсию для обхода дерева (направленный граф) для получения родственников для заданного человека, а потом ищем в нем того с чем определяем родство....


Полное решение будет стоит 250WMR. Обращайтесь.

понедельник, 17 мая 2010 г.

как поменять элементы массива местами c

как поменять элементы массива местами (Си)

самый простой способ для понимания это представить себе переменную в виде стакана с водой

итого мы имеем 2 стака с жидкостями которые нужно поменять местами (содержимое стакана)

как бы вы сделали это в реальной жизни? так же и в программе! - посредством третьего стакана!


int a = 10;
int b = 20;
int temp; //наш третий стакан - посредник

temp = a; //перелили в третий стакан содержимое первого
a = b; //первый у нас освободился? заполняем его содержимым второго
b = temp; //второй освободился? заполняем его содержимым третьего (а там что?)

вот и поменялись...

javascript нахождение суммы цифр числа

javascript нахождение суммы цифр числа

<script>
var n = prompt ("number?", "1234")
var s = 0

while (n > 0)
{
 s += n % 10
 n = Math.floor(n/10)
}

alert("summa: " + s)
</script>

вторник, 11 мая 2010 г.

нерешенные еще проблемы

  • распаковка rar файлов с русскими именами файлами в ubuntu 10.04

понедельник, 10 мая 2010 г.

количество счастливых билетов

Кто возьмет билетов пачку, тот получит водокачку!

Нужно посчитать и вывести на экран количество "счастливых билетов"(к примеру: 111201, 333009 и так далее)

Примечание :

Счастливый билетик имеет вид XXXXXX.

var
    a,b,c,d,e,f: integer;
    g: double;
begin
    g:=0;
    for a:=0 to 9 do
    for b:=0 to 9 do
    for c:=0 to 9 do
    for d:=0 to 9 do
    for e:=0 to 9 do
    for f:=0 to 9 do
    if a+b+c=d+e+f then g:=g+1;
    writeln(g);
end.

PS: обычно я решаю сам, а этот пример подсмотрел - уж очень мне понравилась простота решения, единственное что я добавил - это g - переменная типа double, т.к. результат получается больше чем может представлять пременная типа int, ну и в оригинале было inc - пришлось сдеать g=g+1, ибо inc только для целочисленной математики, еще бы полагалось выводить знаки только до запятой (число то все равно целое), но это уже сами кому надо...

вывести матрицу из файла с++

вывести матрицу из файла с++

часто встречаю подобные задачи, вот один из способов реализации

отмечу только, что раз мы считываем матрицу из файла - то мы заранее
не знаем ее размер, а раз так - то память под неё мы выделяем динамически
с помощью оператора new (не забываем освобождать после использования)

и нужно придумать в каком виде хранить матрицу

создадим текстовый файл matrix.txt
с таким содержанием
2 3
1 2 3
4 5 6

в нем первая строка содержит два числа,
первое - количество строк матрицы, второе кол-во столбцов

#include <stdio.h>

int main(int argc, char * argv[])
{
 int n = 0;
 int m = 0;

 int **a;

 //открываем файл
 FILE * fp = fopen("matrix.txt", "r");
 if (fp)
 {
  //читаем количество строк и столбцов
  fscanf(fp, "%d %d", &n, &m);

  //выделяем место
  *a = new int(n);
  for (int i = 0; i < n; i++) a[i] = new int(m);

  //считываем данные из файла в матрицу
  for (int i = 0; i < n; i++)
  {
   for (int j = 0; j < m; j++)
   {
    fscanf(fp, "%d", &a[i][j]);
   }
  }
  
  //закрываем файл
  fclose(fp);
 }

 //печать матрицы
 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < m; j++)
  {
   printf("%d ", a[i][j]);
  }

  printf("\n");
 }

 //освобождение памяти
 for (int i = 0; i < n; i++) delete a[i];
 delete *a;


 return 0;
}

и вот вывод программы

1 2 3
4 5 6

перевод чисел из двоичной системы в текст

/* перевод чисел из двоичной системы в текст */

#include <stdio.h>

void main()
{
 int n = 1234;
 int i = 0;
 int m[32];

 printf("10: %d\n", n);

 while (n > 0)
 {
  m[i++] = n & 1;
  n = n >> 1;
 }

 printf(" 2: ");

 for (; i > 0; i--)
 {
  printf("%d", m[i-1]);
 }

 printf("\n");
}

массив состоит из 20 целых положительных и отрицательных чисел. выведите на экран сначала отрицательные, а затем положительные числа.

/* массив состоит из 20 целых положительных и отрицательных чисел.
 выведите на экран сначала отрицательные,
 а затем положительные числа. */

#include <stdio.h>

void main()
{
 int m[] = {1, -2, 3, 4, 5, 6, 7, 8, -9, 10, 11, -12, 13, 14, -15, 16, 17, -18, 19, 20};
 int i;

 printf("отрицательные: ");
 for (i = 0; i < 20; i++)
  if (m[i] < 0)
   printf("%d ", m[i]);

 printf("\n");


 printf("положительные: ");
 for (i = 0; i < 20; i++)
  if (m[i] > 0)
   printf("%d ", m[i]);

 printf("\n");
}

четверг, 6 мая 2010 г.

найти сумму цифр в числе используя рекурсивную подпрограмму

для простоты будем считать что числа только натуральные

function fun(x:integer; summa: integer) : integer;
var
   d, m: integer;
begin
   m := x mod 10;
   d := x div 10;
   if x > 0
   then fun := fun(d, summa + m)
   else fun := summa + m;
end;

begin
   writeln('cумма цифр = ', fun(1234, 0));
end.

среда, 28 апреля 2010 г.

Нахождение корня функции.

Здесь описан метод половинного деления (дитохомии?). Суть проста. Есть функция f(x), есть интервал [a,b], есть условие, что на концах промежутка функция имеет разный знак: f(a)*f(b)<0. Требуется найти с заданной точностью eps корень этой функции. Поступаем так: выбираем середину отрезка [a,b]. Если в середине функция имеет тот же знак что и слева, то принимаем середину за новую левую границу, в противном случае - за правую. Повторяем до тех пор, пока отрезок не станет меньше eps. В данном примере в качестве функции берем синус, а отрезок - [3,4]. Таким образом мы должны найти число пи.

function f(x:real):real;
  begin
  f:=sin(x);
  end;
const MaxSteps=200;
var a0,b0,a,b,eps,fa,fb,t,ft:real;
    step,sa,sb:integer;
begin
writeln('Нахождение корней функции методом половинного деления:');
a0:=3; {writeln(' Input a0: ');readln(a0);}
b0:=4; {writeln(' Input b0: ');readln(b0);}
eps:=0.0000001; {writeln(' Input eps: ');readln(eps);}
fa:=f(a0); fb:=f(b0);
if (fa*fb>0) then
  begin
  writeln(' На заданном промежутке корней нет.');
  halt;
  end;
a:=a0; b:=b0;
step:=0; t:=a; ft:=fa;
while (abs(b-a)>eps) and (step<MaxSteps) do
  begin
  inc(step);
  t:=(a+b)/2;
  ft:=f(t);
  if (fa*ft>0) then
    begin
    fa:=ft;
    a:=t;
    end
  else
    b:=t;
  writeln('step:',step:4,' t=',t,' f(t)=',ft);
  end;
if (step>MaxSteps)
  then writeln('Отсутствие сходимости. Уточните промежуток.')
  else writeln('Найден корень с заданной точностью.');
end.

нахождения корней уравнения методом половинного деления



PROGRAM KORNI;
VAR A,B,PREC:REAL;
FUNCTION F(X:REAL):REAL;
BEGIN
 F:=X*X-3*X+2
END;
FUNCTION KORENJ(A,B,PREC:REAL):REAL;
VAR X,Y,Z:REAL;
BEGIN
 IF ABS(A-B)<PREC THEN KORENJ:=(A+B)/2
   ELSE BEGIN
   X:=F(A);
   Y:=F((A+B)/2);
   Z:=F(B);
   IF X*Y<0 THEN KORENJ:=KORENJ(A,(A+B)/2,PREC)
            ELSE KORENJ:=KORENJ((A+B)/2,B,PREC)
   END
END;
BEGIN
 READLN (A,B,PREC);
 WRITELN ('X=',KORENJ(A,B,PREC))
END.

вторник, 27 апреля 2010 г.

определитель матрицы

и снова определитель матрицы


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int n = 4;

void print(int**, int);
void clear(int**, int**, int, int, int);
long Determinant(int**, int);

void main()
{
 time_t t;
 srand(time(&t));

 int** a = new int*[n];
 for (int i = 0; i < n; i++) a[i] = new int[n];


 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < n; j ++)
  {
   a[i][j] = rand() % 10;
  }
 }

 print(a, n);

 long dt = Determinant(a, n);
 printf("\nDeterminant = %d\n", dt);

 for (int i = 0; i < n; i++) delete[] a[i];
 delete[] a;
}

void print(int** a, int n)
{
 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < n; j++)
  {
   printf("%d\t", a[i][j]);
  }

  printf("\n");
 }
}

void clear(int** a, int** b, int m, int i, int j)
{
 int di = 0;
 int dj;

 for (int ki = 0; ki < m - 1; ki++)
 {
  if (ki == i)
   di = 1;

  dj = 0;
  for (int kj = 0; kj < m - 1; kj++)
  {
   if (kj == j)
    dj = 1;

   b[ki][kj] = a[ki + di][kj + dj];
  }
 }
}

long Determinant(int** a, int n)
{
 if (n == 1)
  return a[0][0];

 if (n == 2)
  return a[0][0] * a[1][1] - a[0][1] * a[1][0];

 int** b = new int*[n];
 for (int i = 0; i < n; i++) b[i] = new int[n];

 int d = 0;
 int k = 1;
   
 for (int i = 0; i < n; i++)
 {
  clear(a, b, n, i, 0);
  d += k * a[i][0] * Determinant(b, n - 1);
  k--;
 }

 for (int i = 0; i < n; i++) delete[] b[i];
 delete[] b;

 return d;
}

понедельник, 26 апреля 2010 г.

борьба с банерами от порно-информермеров

Конечно никто не хочет себе такие красОты, но когда они появляются, то хочется по скорее от них избавиться...

Наши Касперские и др. не спят и уже придумали генераторы кодов для снятия блокировок.

Здесь представлены генераторы кодов от разных производителей:

понедельник, 12 апреля 2010 г.

полезные скрипты для bash

замена переводов строк на запятую
$ awk '{printf $0","}' input.txt > output.txt

размер директории (заметьте - новый формат в системе CИ)
$ du --si

пятница, 26 марта 2010 г.

среднее арифметическое введенных чисел

Создайте сценарий, который будет выводить среднее арифметиское из неограниченного числа, введенных пользователем значений. Ввод будет продолжаться до тех пор пока не будет введен 0. После ввода 0 программа будет выводить на экран все введенные числа и подститанное значение средного арифметического из этих чисел.

var summa = 0;
var n = 0;
while (true)
{
 var x = prompt('input x:');
 if (x == 0)
  break;

 summa += parseInt(x);
 document.write(x);
 document.write("<br>");
 n++;
}

if (n != 0)
{
 document.write("----<br>avg=");
 document.write(summa/n);
}


тут можно качнуть скипт