site logo
  • Կայքի մասին
  • Ծրագրավորում
  • Ժեշտ
  • Անվտանգություն
  • Հարց ու Պատասխան (ՀուՊ)
Հոկտեմբեր 30, 2012  |  By armenbadal In

Մեկ օրինակ հինգ լեզուներով

Այս հոդվածի համար ես ընտրել եմ պատկերի մակերեսի հաշվման թվային մի եղանակ, որ ավելի հայտնի է “Մոնտե-Կառլոյի մեթոդ” անվանբ։ C, Java, Go, Common Lisp և C++11 լեզուներով ես կներկայացնեմ թվային ինտեգրման այս եղանակի իրականացումը։

Ենթադրենք տրված է մի P պատկեր, որի մակերեսն ուզում ենք հաշվել։ Ընդգրկենք այդ պատկերը a կողմով A քառակուսու մեջ, որի ներքևի ձախ անկյունը տեղադրված է կոորդինատների սկզբնակետում։ Պատահականորեն ընտրենք քառակուսու մեջ ընկած N կետեր և հաշվենք, թե դրանցից քանիսն են պատկանում P պատկերին. նշանակենք այդ քանակը n0։ Ըստ Մոնտե-Կառլոյի մեթոդի, P պատկերի մակերեսի հարաբերությունը A քառակուսու մակերեսին պետք է հավասար լինի N-ի արաբերությանը n0-ին։

S_P = S_A\frac{n_0}{N}

Ծրագրավորման տեսակետից, պետք է սահմանել մի ֆունկցիա, որ ստանում է P պատկերը բնութագրող ֆունկցիան, A քառակուսու կողը՝ a, և պատահականորեն ընտրվող կետերի քանակը N, ապա հաշվարկում և վերադարձնում է պատկերի մակերեսը։ Պատկերը բնութագրող ֆունկցիան պետք է պատասխանի արդյո՞ք տրված կետն ընկած է պատկերի վրա, թե՝ ոչ։

Որպես օրինակ վերցնենք f(x)=x2 ֆունկցիան և հաշվենք նրա ինտեգրալը [-2;2] միջակայքում։ Նախ հաշվենք մաթեմատիկական եղանակով.

այս արժեքը կարելի է օգտագործել նաև որպես ծրագրերի ստուգման միջոց։

Ինչպես ասվեց վերևում, Մոնտե-Կառլոյի մեթոդի կիրառման համար ընդգրկող քառակուսին պետք է ընկած լինի առաջին քառորդում (սա, իհարկե, արված է պարզության համար, պարզ է որ կարելի է վերցնել կամայական քառակուսի կամ ուղղանկյուն, կամ մի այլ պատկեր, որի մակերեսը հեշտ է հաշվել)։ Դրա համար տեղաշարժենք f(x)=x2 ֆունկցիայի գրաֆիկն այնպես, որ [-2;2] միջակայքում ընկած հատվածև տեղափոխվի առաջին քառորդ։ Այդ նոր ֆունկցիան կարտահայտվի f(x)=(2-x)2 բանաձևով, և հենց այս բանաձևն էլ կօգտագործվի որպես բնութագրող ֆունկցիա։


Սկսենք C լեզվից։ Պատահական թվերը գեներացվում են rand ֆունկցիայով, որը վերադարձնում է [0; RAND_MAX) միջակայքի պատահական ամբողջ թիվ։ [0; a) միջակայքի պատահական թվեր ստանալու համար սահմանված է հետևյալ ֆունկցիան.

/**/
double random(double s)
{
	return s * ((double)rand() / RAND_MAX); 
}

C լեզվում բարձր կարգի ֆունկցիաներ չկան և բնութագրող ֆունկցիան պետք է փոխանցել ցուցիչի տեսքով։

/**/
double monteCarloMethod(int(*f)(double,double), double a, int n)
{
	int no = 0;
	while( n-- > 0 )
		if( f( random(a), random(a) ) )
			++no;
	return a * a * no / n;
}

Բնութագրող ֆունկցիայի սահմանումը նույնպես պարզ է.

/**/
int parabola(double x, double y)
{
	double e = 2.0 - x;
	return e * e > y;
}

main ֆունկցիան պարզապես կանչում է monteCarloMethod ֆունկցիան, նրան փոխանցելով պարաբոլը բնութագրող ֆունկցիայի հասցեն, ընդգրկող քառակուսու կողը՝ 4, և պատահական ընտրվող կետերի քանակը։

/**/
int main()
{
	srand(time(0));
	double res = monteCarloMethod(&parabola, 4.0, 10000);
	printf("%f\n", res);
	return 0;
}

Java լեզվով խնդրի լուծումը ներկայացնեմ որպես ամբողջական ֆայլ, որի մեջ գրված են անհրաժեշտ մեկնաբանությունները։

package montecarlo;

import java.util.Random;

public class MonteCarlo {
	// պատահական թվերի գեներատոր
	private static Random generator = new Random();

	// Այս ինտերֆեյսը սահմանված է բնութագրող ֆունկցիաների համար։ 
	// check ֆունկցիայի իրականացումը կպարունակի բուն բնութագրիչը։
	private interface Characteristic {
		boolean check(double x, double y);
	}

	// Characteristic ինտերֆեյսի իրականացումն է քառակուսային ֆունկցիայի համար։
	//   Այս դասի նմուշը կոգտագործենք հաշվարկների համար։
	private class Quadratic implements Characteristic {
		@Override
		public boolean check(double x, double y)
		{
			double e = 2.0 - x;
			return e * e > y;
		}
	}

	// Պատահական թվի մասշտաբավորում մեր միջակայքի համար։ 
	private static double rnd(double a)
	{
		return a * generator.nextDouble();
	}

	// Մոնտե-Կառլոյի մեթոդը։ 
	private static double monteCarloMethod(Characteristic f, double a, int n)
	{
		int no = 0; // պատկերի ներսում ընկած թվերը
		for( int i = 0; i < n; ++i )
			// բնութագրիչի կիրառում պատահական կոորդինատների համար
			if( f.check(rnd(a), rnd(a)) )
				++no;
		// մակերեսի հաշվարկ
		return a * a * no / n; 
	}

	/**/
	public static void main(String[] args) 
	{
		Quadratic f = (new MonteCarlo()).new Quadratic();
		double res = monteCarloMethod(f, 4, 1000);
		System.out.println(res);
	}

}

Go լեզվով ծրագիրն արդեն բավականին կոմպակտ է։ Նախ սահմանենք բնութագրիչ ֆունկցիայի տիպը։

type XYPredicate func(float64,float64) bool

Բուն մեթոդն ունի ահա այսպիս տեսք.

// Monte-Carlo method.
func monteCarloMethod(f XYPredicate, a float64, n int) float64 {
	// պատկերի ներսում ընկած կետերի քանակը
	var no int
	for i := 0; i < n; i++ {
		// պատահական կետի կոորդինատներ
		x := a * rand.Float64()
		y := a * rand.Float64()
		// բնութագրիչի ստուգում
		if f(x,y) { no++ }
	}
	// մակերեսի հաշվարկ
	return (float64(no) * a * a) / float64(n)
}

Պարաբոլի բնութագրող ֆունկցիան։

func parabola(x, y float64) bool {
	e := 2.0 - x
	return e * e > y
}

Եվ կիրառումը.

func main() {
	k := monteCarloMethod(parabola, 4.0, 10000)
	fmt.Println(k)
}

Common Lisp լեզվով իրականացումն իհարկե ամենագեղեցիկն է։ Միայն loop մակրոսի մեկ կիրառությամբ ծրագրավորված է ալգորիթմը։ Իմ կարծիքով, արտահայտված է նաև սեմանտիկան.

(defun monte-carlo-method (f a &optional (n 100))
  (loop repeat n ; կրկնել n անգամ
        with no = 0 ; պատկերի կետերի քանակը
        when (funcall f (random (float a)) (random (float a))) ; պայմանի ստուգում
        do (incf no) ; կետերի քանակի վերահաշվարկ
        finally (return (/ (float (* a a no)) n))))

Պարաբոլը բնութագրող ֆունկցիան է։

(defun parabola (x y)
  (let ((e (- 2 x)))
    (> (* e e) y)))

Արժեքի հաշվարկ և արտածում։

(print (monte-carlo-method #'parabola 4 10000))

Եվ վերջապես, C++11 իրականացումը։

/**/
double monteCarloMethod( std::function<bool(double,double)> f, double a, unsigned int n )
{
	std::random_device dev;
	std::default_random_engine eng(dev());
	std::uniform_real_distribution<double> distr(0.0, a);
	//
	unsigned int no(0);
	for( unsigned int i = 0; i < n; ++i )
		if( f( distr(eng), distr(eng) ) ) ++no;
	//
	return a * a * no / n;
}

 

/**/
bool parabola(double x, double y)
{
	double e(2.0 - x);
	return e * e > y;
}

 

/**/
int main()
{
	std::cout << monteCarloMethod(parabola, 4.0, 10000) << std::endl ;
	return 0;
}

Բացատրությունները ապագայում 🙂

Մեկ օրինակ հինգ լեզուներով, 10.0 out of 10 based on 7 ratings
C++ Common Lisp go high-order function integral Java random Ծրագրավորման լեզուներ Մոնտե-Կառլոյի մեթոդ
Previous StoryՀնարավորթյունների էքստրերմումի մասին կամ նոր էքսելյան մուտիլովկաներ
Next Story168.am-ը մեր կայքի մասին

Comments: 3 replies added

  1. Արտակ Կոլյան Հոկտեմբեր 30, 2012 Մեկնաբանել

    Շնորհակալություն, լավ նյութ է

  2. Արթուր Նոյեմբեր 6, 2012 Մեկնաբանել

    Այ հիանում եմ ․․․ Go, Common Lisp ... Վերջապես ․․․ Կար ժամանակ երբ մենակ եփվում էի PLAN9/Inferno , մեկ-մեկ էլ QNX ի գրկում․ ՈՒ մեկը չկար բան քննարկեի ։-) Հետաքրքիր ա, Erlang ը կա՞ էս շարքում։ Հ․Գ․ Հուսով եմ երևում ա, թե մտքիս թելը ուր ա գնում

    • armenbadal Նոյեմբեր 6, 2012 Մեկնաբանել

      Շնորհակալություն դրական արձագանքի համար :) Անկեղծ ասած, վաղուց պլանավորում եմ ծանոթանալ Erlang-ի հետ, բայց ինչ-որ չի ստացվում (ժամանակի տեսակետից)։ Հիմա ամբողջ ազատ ժամանակս կլանում է Common Lisp լեզվի մասին հայերեն գիրքը, որ նախաձեռներլ եմ մի քանի ամիս առաջ, և Go լեզվի նախնական ուսումնասիրությունը։ Երևի առաջիկայում այս կայքում կհայտնվեն առավելապես Common Lisp, Go, C++ լեզուներին առնչվող հոդվածներ։

Join in: leave your comment Cancel Reply

(will not be shared)

Որոնում

Նշագրեր

*Nix-եր (18) android (17) C++ (19) C և C++ (27) Excel (10) html (10) Network Administration (16) System Administration (28) Windows 7 (14) Ալգորիթմներ (15) Անվտանգություն (29) ԳՆՈՒ/Լինուքս (16) Թեյնիկներին (57) Ժեշտ (44) Լակոնիկ (21) Լինուքս/Յունիքս հրամաններ (29) Լուսանկարչություն և մշակում (15) Խելախոսներ (19) Ծրագրավորման լեզուներ (16) Ծրագրավորում (64) Ծրագրեր (48) Հայականացում (28) Հումոր (11) Ուսումնական նյութեր (34) Սոցցանցային Հմտություններ (19) Վեբ (25) Վերլուծություն (10) Վորդպրես (21) ՏՏ և փիլիսոփայություն (21) Տվյալների բազաներ (12) Օպերացիոն համակարգեր (27) Օֆիսային ծրագրեր (22) անդրոիդ (16) բաշ (10) ինտերնետ (11) խելախոսներ (13) համացանց (15) հայատառ (10) հայերեն (11) հայերեն ստեղնաշար (11) հայկական սոֆթ (11) ստեղնաշար (10) սքրիփթ (14) վինդոուս (12) տեսանյութ (23)
Copyright ©2017 ThemeFuse. All Rights Reserved