Типичные задачи и примеры. Теория.

[Stilet]

Дописано 24 12 2010

В массивы вводятся элементы двух невозрастаюших последовательностей Ai и Bj целых чисел, которые содержат 6 и 8 элементов соответственно. Необходимо вывести на экран общий список значений элементов этих последовательностей по их возрастанию без создания третьего массива.

Предлагаемое решение:
http://www.programmersforum.ru/showthread.php?t=129806

[Stilet]

Си. Пример сортировки пузырьком

// qweqwe.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <stdlib.h>
#include <math.h>
int _tmain(int argc, _TCHAR* argv[])
{
	//Упорядочить элементы массива по Возростанию элементов.
	const int n=5;
	int a[n];
	for(int i=0;i<n;i++){
			a[i]=rand()-rand();
			printf("%d\t",a[i]);
	};printf("\n");
// Сортир пузырьком
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if (a[i]<a[j]){
				int o=a[i];a[i]=a[j];a[j]=o;
			};
 		};
	};
//Вывод
	printf("\n");
	for(int i=0;i<n;i++){
			printf("%d\t",a[i]);
	};printf("\n");

	getchar();
	return 0;
}

[Stilet]

Проход по элементам над и под диагоналями

// Над и под диагоналями матрицы.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"


int _tmain(int argc, _TCHAR* argv[])
{
	const int n=5,m=5;
	int a[n][m];
	// Вводим матрицу
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			a[i][j]=i+j;printf("%d\t",a[i][j]);
		}printf("\n");
	}printf("\n");

	//Проход под главной диагональю
	for(int i=1;i<n;i++){
		for(int j=0;j<i;j++){
			//a[i][j] указывает на элемент ниже главной диагонали
		};
	};

	//Проход над главной диагональю
	for(int i=0;i<n;i++){
		for(int j=(i+1);j<m;j++){
			//a[i][j] указывает на элемент выше главной диагонали
		};
	};

	//Проход под Побочной диагональю
	for(int i=1;i<n;i++){
		for(int j=m;j>(m-i);j--){
			//a[i][j] указывает на элемент ниже побочной диагонали
		};
	};

	//Проход над Побочной диагональю
	for(int i=0;i<n;i++){
		for(int j=i;j<(m-i);j++){
			//a[i][j] указывает на элемент выше побочной диагонали
		};
	};

	return 0;
}

Собрано в VS2010Beta

[Stilet]

Шринковка массива - Удаление из него элементов, отвечающих некому условию:

// Уаплить из массива элементы по условию.cpp: определяет точку входа для консольного приложения.
//http://www.programmersforum.ru/showthread.php?p=711868#post711868

#include "stdafx.h"
#include <malloc.h>
#include<stdlib.h>

int *a;
int n=10;

bool Удалить(int i){
	// Например удалить все четные	return !(a[i]%2);
	// Или те которые встречаются более 2 раз
	int c=0;
	for(int k=0;k<n;k++) c+=(a[i]==a[k])?1:0;
	return (c>2);
}

int _tmain(int argc, _TCHAR* argv[])
{
	srand(1000);
	// Задаем массив
	a=(int*)malloc(n*sizeof(int));
	// Вводим массив
	for(int i=0;i<n;i++){
		a[i]=rand()%8;printf("%d\t",a[i]);
	} printf("\n");
	// Шринкуем массив
	int k=0;
	for(int i=0;i<n;i++){
		a[k]=a[i];
		k+=(Удалить(i))?0:1;
	} printf("\n");
	// Выводим шринкованный массив
	for(int i=0;i<k;i++){
		printf("%d\t",a[i]);
	} printf("\n");
	// Освобождаем массив
	free(a);
	getchar();
	return 0;
}

Собрано в VS2010Beta

[Stilet]

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

Пример работы с динамическим списком в С++

в прилагаемом файле с коментариями. Увы весь код сюда в пост не влезает.
Писано для С++. Для классического Си. придется менять cout на printf() и new на malloc();

[Stilet]

Метод бинарного поиска

program Project1;

{$APPTYPE CONSOLE}
         {$o-}
uses
  SysUtils;
var a:array[1..100] of integer;
    i:integer;

 function SelectIndexByBinary(Value:integer):integer;
 var c,b,i,stp:integer;
 begin
  b:=1;c:=100;Result:=-1;stp:=0;
  { Начинаем цикл пока разница между границами не будет равна 2 что
  скажет о том что искать больше нечего, т.е между граничными элементами
  уже ничего нет}
  while (c-b)>2 do begin
  {Это колво шагов для статистики}
    inc(stp);
    {Становимся посередине искомого подмассива}
    i:=b+(c-b) div 2;
    {если найден то выйти вернув номер найденого по порядку}
    if a[i]=Value then begin Result:=i; break;;end;
    {иначе сравним}
    if a[i]>Value then
     {Если искомое меньше центрального то сдвигаем верхнюю границу
     Считая что за центром искомого нет и быть не может}
     c:=i
    else
     {Иначе искомого нет слева от центра, тогда сдвигаем нижнюю границу}
     b:=i;
  end; writeln;writeln('Steps of Maya =',stp);
 end;

begin
{Наполняем или сортируем массив Не важно как}
 a[1]:=1;
 for i:=2 to 100 do begin
  a[i]:=random(10)+a[i-1];write(a[i]:5);
 end;
 writeln;
{Пробуем отискать бинарным поиском}
 write(SelectIndexByBinary(9));readln;
  { TODO -oUser -cConsole Main : Insert code here }
end.

[Stilet]

Си классический
Вращение, сдвиг, умножение матриц

#include "stdafx.h"
#include <malloc.h>
#include <stdlib.h>

//Описываем структуру матрицы
struct TMatrix{
	int **Array; //Тело матрицы
	int Rows;  //Кол-во строк
	int Columns; //Колонок
};

//Процедура создания матрицы по ссылке
void CreateMatrix(TMatrix &Matrix, int Rows, int Cols){
	//Выделяем память под строки
	Matrix.Array=(int**)malloc(sizeof(int)*Rows);
	//В цикле
	for(int i=0;i<Rows;i++){
		//Выделяем память под колонки каждой строки
		Matrix.Array[i]=(int*)malloc(sizeof(int)*Cols);
		//И наполняем их
		for(int j=0;j<Cols;j++){
			Matrix.Array[i][j]=i*10+j+1;//rand()/1000;
		}
	}
	//Запомнив размерность
	Matrix.Rows=Rows;
	Matrix.Columns=Cols;
}

//Печать мтарицы на экран
void WriteMatrix(TMatrix Matrix){
	for(int i=0;i<Matrix.Rows;i++){
		for(int j=0;j<Matrix.Columns;j++){
			printf("%5d",Matrix.Array[i][j]);
		} printf("\n");
	}printf("\n");
}

//Перемножение матриц
void MatrixMultiple(TMatrix MatrixA,TMatrix MatrixB,TMatrix &MatrixC){
	int Rows=MatrixA.Rows;
	int Cols=MatrixA.Columns;
	//Создается отдельная матрица, в которую будет сбрасываться результат умножения
	//элементов
	CreateMatrix(MatrixC,Rows,Cols);
	for(int i=0;i<Rows;i++){
		for(int j=0;j<Cols;j++){
			//В цикле элементы умножаются друг на друга
			MatrixC.Array[i][j]=MatrixA.Array[i][j]*MatrixB.Array[i][j];
		}
	}
}

//Освобождение матрицы (Не работает!)
void FreeMatrix(TMatrix &Matrix){
	
	//for(int i=1;i<=Matrix.Rows;i++)	free(Matrix.a[i]);
	free(Matrix.Array);
	Matrix.Columns=0; Matrix.Rows=0;
	
}

//Сдвиг (вращение) матрицы по горизонтали на N колонок
void ShiftHoriz(TMatrix &Matrix, int n){
	//Сдвиг циклический.
	n=(n>Matrix.Columns)?n%Matrix.Columns:n;
	//Создаем временный буффер для данных
	int* buf=(int*)malloc(sizeof(int)*n);
	for(int i=0;i<Matrix.Rows;i++){
			//Части строки меняем местами согласно кличеству сдвигаемых элементов
		   //черех вспомагательный буффер
			memcpy(buf,&Matrix.Array[i][0],sizeof(int)*n);
			memcpy(&Matrix.Array[i][0],&Matrix.Array[i][n],sizeof(int)*(Matrix.Columns-n));
			memcpy(&Matrix.Array[i][Matrix.Columns-n],buf,sizeof(int)*n);
	}
	delete buf;
}

//Сдвиг вертикально (вращение тоже)
void ShiftVert(TMatrix &Matrix, int n){
	n=(n>Matrix.Rows)?n%Matrix.Rows:n;
	int** buf=(int**)malloc(sizeof(int)*n);
	for(int i=0;i<n;i++){
		buf[i]=(int*)malloc(sizeof(int)*Matrix.Columns);
		memcpy(&buf[i],&Matrix.Array[i][0],sizeof(int)*Matrix.Columns);
	}
	for(int i=n,j=0;i<Matrix.Rows;i++,j++)	    memcpy(&Matrix.Array[j][0],&Matrix.Array[i][0],sizeof(int)*Matrix.Columns);
	for(int i=Matrix.Rows-n,j=0;i<Matrix.Rows;i++,j++)	memcpy(&Matrix.Array[i][0],&buf[j],sizeof(int)*Matrix.Columns);
	//for(int i=0;i<n;i++) delete buf[i]; 
	delete buf;
}

// Поворот матрицы
void RotateOn90(TMatrix &MatrixA,TMatrix &MatrixB){
	CreateMatrix(MatrixB,MatrixA.Columns,MatrixA.Rows);
	// и укажем координаты начального элемента
	// поскольку циклами проходиться будем по старой матрице
	int x=0,y=0,i;
	for(int j=0;j<MatrixA.Columns;j++){
		for(i=MatrixA.Rows-1;i>=0;i--){
			MatrixB.Array[y][x++]=MatrixA.Array[i][j];
		}; y++;x=0;
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	TMatrix a,b,c,d;
	CreateMatrix(a,6,3);WriteMatrix(a);	
	CreateMatrix(b,6,3);WriteMatrix(b);
	MatrixMultiple(a,b,c);WriteMatrix(c);

	ShiftHoriz(a,1); WriteMatrix(a);

	ShiftVert(a,1); WriteMatrix(a);
	RotateOn90(c,d); WriteMatrix(d);
	
	FreeMatrix(a);FreeMatrix(b);FreeMatrix(c);
	getchar();
	return 0;
}

VS2010Beta

[Zer0]

Основная реализация XOR-списка
Реализовано - добавление в конец списка, получение предыдущей/следующей пары элементов, удаление произвольного элемента, очистка списка, вывод списка

type
 TListData = integer;

 TXNode = ^TNode;
 TNode = record
  addr:longint;
  data:TListData;
 end;

 TXList = record
  XStart,XEnd:TXNode;
 end;

procedure AddToList( Data:TlistData; var List:TXList);
var t:TXNode;
begin
  if (List.XEnd=nil) then begin
    new(t);
    t^.data:=Data;
    T^.addr:=longint(nil) xor longint(nil);
    List.XStart:=t;
    List.XEnd:=t;
  end else begin
    new(t);
    t^.data:=Data;
    t^.addr:=longint(List.XEnd) xor longint(nil);
    List.XEnd^.addr:=(Longint(List.XEnd^.addr) xor Longint(nil)) xor Longint(t);
    List.XEnd:=t;
  end;
end;

procedure GetNextPair(var n1,n2:TXNode);
var t:TXNode;
begin
   t:=n2;
   n2:=Pointer(n2^.addr xor longint(n1));
   n1:=t;
end;

procedure GetPrevPair(var n1,n2:TXNode);
var t:TXNode;
begin
   t:=n1;
   n1:=Pointer(n1^.addr xor longint(n2));
   n2:=t;
end;

function DeleteFromList(Index:integer; var List:TXList):boolean;
var cn,t1,t2:TXNode; i:integer; a1,a2:longint;
begin
  t1:=nil;
  t2:=List.XStart;
  i:=1;
  while (t2<>nil) and (i<Index) do begin
    inc(i);
    GetNextPair(t1,t2);
  end;
  if t2=nil then DeleteFromList:=false else begin
    DeleteFromList:=true;
    cn:=t2;
    t2:=Pointer(longint(t1) xor cn^.addr);
    if (t1=nil) and (t2=nil) then begin
      List.XStart:=nil;
      List.XEnd:=nil;
    end else
    if (t1=nil) then begin
      List.XStart:=t2;
      t2^.addr:=(Longint(cn) xor t2^.addr) xor Longint(nil);
    end else
    if (t2=nil) then begin
      List.XEnd:=t1;
      t1^.addr:=(Longint(cn) xor t1^.addr) xor Longint(nil);
    end else begin
      a2:=(Longint(cn) xor t2^.addr) xor Longint(t1);
      a1:=(Longint(cn) xor t1^.addr) xor Longint(t2);
      t1^.addr:=a1;      t2^.addr:=a2;
    end;
    dispose(cn);
  end;
end;

procedure ClearList(var List:TXList);
var t2,t:TXNode; t1:longint;
begin
 t1:=longint(nil);
 t2:=List.XStart;
 while t2<>nil do begin
  t:=t2;
  t2:=Pointer(longint(t2^.addr) xor t1);
  t1:=longint(t);
  dispose(t);
 end;
 List.XStart:=nil;
 List.XEnd:=nil;
end;

procedure PrintList(List:TXList);
var t1,t2:TXNode;
begin
  t1:=nil;
  t2:=List.XStart;
  while t2<>nil do begin
    write (t2^.data,' ');
    GetNextPair(t1,t2);
  end;
  writeln;
end;

var L:TXList; i,t:integer;

begin
  randomize();
  writeln ('Adding numbers: ');
  for i:=1 to 10 do begin
    t:=random(100);
    write(t,' ');
    AddToList(t,l);
  end;
  writeln;
  writeln ('List: ');
  PrintList(L);
  while L.XStart<>L.XEnd do begin
  t:=random(10)+1;
  if DeleteFromList(t,L) then
  writeln ('Delete ',t,' elem')
  else writeln ('Out of index! (',t,')');
  writeln ('List after delete: ');
  PrintList(L);
  end;
  ClearList(L);
  readln;
end.

[Вадим Мошев]

ИМХО, для того, чтобы лучше понять работу с матрицами (как двумерными массивами), сначала надо освоить работу над одномерными массивами, поскольку такой тип данных требует меньше времени на разработку обрабатывающих их алгоритмов, а чисто психологически, вызывает меньше страха у начинающих. При переходе к массивам с бОльшим числом измерений все принципы работы сохраняются.

Циклический сдвиг элементов одномерного массива.

Циклическим сдвигом элементов одномерного массива называется такое изменение порядка следования элементов, при котором каждый его элемент становится на позицию элемента, предшествующего/следующего за текущим, а первый/последний элемент массива становится последним/первым. Например, если речь идёт о циклическом сдвиге впёрёд, то определение сдвига принимает следующий вид: Циклическим сдвигом вперёд элементов одномерного массива называется такое изменение порядка следования элементов, при котором каждый его элемент становится на позицию элемента, следующего за текущим, а последний элемент массива становится первым.

Всё это выглядит следующим образом. Если исходный массив имеет вид:

1 2 3 4 5 6 7 8 9 0

,
То массив, над которым была выполнена операция циклического сдвига вперёд, будет иметь вид:

0 1 2 3 4 5 6 7 8 9

Идея такова (циклический сдвиг вперёд).
1. Запоминаем первый элемент массива в некоторой буферной переменной.
2. Обходим массив от конца к началу, делая так, чтобы каждый элемент массива стал равен предыдущему (как вариант, можно начать обход с предпоследнего до первого)
3. Заменяем первый элемент массива на значение буферной переменной.

Реализация на Pascal.

{Пусть A - массив, состоящий из N элементов}

{Запоминаем последний элемент массива, чтобы в конце поставить его на первое место}
	tmp := a[N];

{Смещаем все элементы массива на 1 позицию вправо}
	for i := N-1 downto 1 do begin
		a[i+1] := a[i]
	end;

{Восстанавливаем первый элемент массива}
	a[1] := tmp;

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

{Пусть A - массив, состоящий из N элементов}

{Запоминаем первый элемент массива, чтобы в конце поставить его на последнее место}
	tmp := a[1];

{Смещаем все элементы массива на 1 позицию влево}
	for i := 1 to N-1 do begin
		a[i] := a[i+1]
	end;

{Восстанавливаем последний элемент массива}
	a[N] := tmp;

[Вадим Мошев]

Перемешивание элементов массива случайным образом.

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

Я предлагаю такое решение.
Сначала следует убедиться, что в массиве содержится более одного элемента, иначе его бессмысленно перемешивать.
Далее стоит проверить, что в массиве более двух элементов. Если в массиве ровно два элемента, то сгенерировать случайное действительное число из диапазона (0; 1), и если это число больше, чем 0.5, то обменять эти два элемента массива значениями.
Если же в массиве содержится более двух элементов, то каждый элемент массива переставляем местами с другим элементом массива, индекс которого равен случайному числу из диапазона индексирования элементов массива (если элементы массива пронумерованы от 1 по N, то диапазон индексирования представляет собой отрезок [1; N]) и в то же время не совпадает с индексом текущего элемента массива.

Реализация на Pascal:

{A - Массив, состоящий из N элементов}

{стоит проверить, что в массиве более двух элементов.  Если в массиве ровно два элемента, то сгенерировать
 случайное действительное число из диапазона (0; 1),  и если это число больше, чем 0.5, то обменять
 эти два элемента массива значениями.}

if N = 2 then begin
  if Random > 0.5 then begin
    tmp := A[0];
    A[0] := A[1];
    A[1] := tmp; 
  end;
end;  
  
{Если же в массиве содержится более двух элементов, то каждый элемент массива переставляем местами с другим
элементом массива, индекс которого равен случайному числу из диапазона индексирования элементов массива
(если элементы массива пронумерованы от 1 по N, то диапазон индексирования представляет собой отрезок [1; N])
и в то же время не совпадает с индексом текущего элемента массива.}  
  
if N > 2 then begin
  for i := 1 to N do begin
    repeat                                         
     k := Random(N) + 1;                                        
    until k <> i;                                         

    tmp := A[i];
    A[i] := A[k];
    A[k] := tmp;
                                                                                                   
  end;
end;

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