Skip to content

Instantly share code, notes, and snippets.

View VardanGrigoryan's full-sized avatar

Vardan VardanGrigoryan

View GitHub Profile
@VardanGrigoryan
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
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
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
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
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
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
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
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
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
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 << " ";
}