VardanGrigoryan’s gists

VardanGrigoryan / Median problem

Last active December 31, 2015 00:39

Տրված են երկու n չափանի սորտավորված զանգվածներ։ Գտնել դրանց միավորումից ստացված զանգվածի մեջտեղի տարրը։ Ալգորիթմի բարդությունը O(logn):

	#include <stdio.h>
	#include <stdlib.h>
	#include <iostream>
	#include <algorithm>

	int get_median(int* a, int s)
	{
	if(s % 2 == 0)
	{
	return (a[s/2] + a[s/2 - 1]) / 2;

VardanGrigoryan / gist:7958104

Created December 14, 2013 11:22

Տրված է երկուական փնտրման ծառ։ Տպել ծառը մակարդակ առ մակարդակ (level order), ալգորիթմի բարդություն է O(n):


	#include <iostream>
	#include <queue>
	#include <stdlib.h>

	struct node
	{
	struct node* left;
	struct node* rigth;
	int data;

VardanGrigoryan / Is path exist

Last active December 31, 2015 08:49

Տրված է միաչափ զանգված, որի տարրերը կարող են լինել 0 կամ 1։ Ընդ որում առաջին տարրը միշտ 0 - է։ Զանգվածը կարելի է շրջանցել, անցնելով միայն 0-ների վրայով, ընդ որում մեկ քայլի երկարությունն է 3 կամ 5 (3 կամ 5 տարր)։ Անհրաժեշտ է գրել ալգորիթմ, որը կստուգի տվյալ զանգվածում առաջին տարրից մինչև վերջին տարր ընկած ճանապարհի առկայությունը։ Պահանջվող ալգոր…

	#include <iostream>
	#include <queue>
	#include <stdlib.h>

	struct node
	{
	struct node* left;
	struct node* rigth;
	int data;
	};

VardanGrigoryan / lca

Created December 15, 2013 16:54

Գտնել երկուական փնտրման ծառում տրված երկու տարրերի ամենափոքր ընդհանուր parent-ը (lowest common ancestor)։ Ալգորիթմի բարդությունը O(n):


	#include <iostream>
	#include <queue>
	#include <stdlib.h>

	struct node
	{
	struct node* left;
	struct node* rigth;
	struct node* parent;

VardanGrigoryan / bst average

Created December 23, 2013 16:38

Տրված է երկուական փնտրման ծառ, որի յուրաքանչյուր հանգույց (node) պարունակում է ինչ-որ ամբողջ թիվ։ Գտնել այդ թվերի միջին թվաբանականը։ Ալգորիթմի պահանջվող բարդությունն է O(n):

	#include <iostream>
	#include <stdlib.h>

	struct node
	{
	struct node* left;
	struct node* right;
	int data;
	};

VardanGrigoryan / ascii_to_bin

Last active January 2, 2016 19:09

ASCII character to binary code

	#include <iostream>

	int main()
	{
	int a[8];
	const char c = 'a';

	for(unsigned int i = 0; i < sizeof(char)*8; ++i)
	{
	if(c & (1 << i))

VardanGrigoryan / heap

Last active January 2, 2016 22:29

Ինչպիսի՞ տվյալների կառուցվածք է առավել հաճախ օգտագործվում նախապատվություններով հերթի կառուցման դեպքում:

	#include <iostream>

	class heap
	{
	private:
	int size;

	private:
	int get_left(int i);
	int get_rigth(int i);

VardanGrigoryan / main.cpp

Created January 26, 2014 17:39

Տրված է չուղղորդված և կշռված գրաֆ, որի բոլոր գագաթների/կողերի կշիռները դրական թվեր են։ Տրված է նաև s բնական թիվը, որը համապատասխանում է գրաֆի մի ինչ-որ գագաթի։ Գտել s գագաթից դեպի մյուս գագաթները ընկած կարճագույն ճանապարհները։


	#include <iostream>
	#include <limits.h>
	#include <stdlib.h>
	#include <queue>

	struct node
	{
	int d;
	int w;

VardanGrigoryan / gist:8899883

Last active January 2, 2022 12:42

Երկու տողերի միջև Լևենշտեյնի հեռավորության որոշում, Վագներ Ֆիշերի ալգորիթմի իրականացում C++ լեզվով


	#include <vector>

	double vagner_fisher_sed_algo(const std::string& s,
	const std::string& d)
	{
	std::vector<std::vector<double> > t(s.length() + 1,
	std::vector<double>(d.length() + 1));
	t[0][0] = 0;
	double o;

VardanGrigoryan / gist:9450697

Last active August 29, 2015 13:57

Փոխարինել հետևյալ ռեկուրսիան իտերացւայով։

	void backtrack(int* a, int k, int n)
	{
	if (k == n)
	{
	for(int i = 1; i <=k; ++i)
	{
	if (a[i] == true)
	{
	std::cout << i << " ";
	}

Vardan VardanGrigoryan