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

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

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

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

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

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

Սկսենք 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