নোড খোঁজার জন্য ইউক্লিডীয় অ্যালগরিদম পাঠের সারাংশ এবং উপস্থাপনা। "ইউক্লিডের অ্যালগরিদম" বিষয়ের উপর উপস্থাপনা: জিসিডি খোঁজার জন্য ইউক্লিডের অ্যালগরিদম

উপস্থাপনাগুলির পূর্বরূপ ব্যবহার করতে, একটি Google অ্যাকাউন্ট (অ্যাকাউন্ট) তৈরি করুন এবং সাইন ইন করুন: https://accounts.google.com

স্লাইড ক্যাপশন:

ইউক্লিডের অ্যালগরিদম ইউক্লিড, প্রাচীন গ্রীক গণিতবিদ। 3য় শতাব্দীতে আলেকজান্দ্রিয়াতে কাজ করেছিলেন। বিসি e প্রধান কাজ "শুরু" (15 বই), যার মধ্যে রয়েছে প্রাচীন গণিতের ভিত্তি, প্রাথমিক জ্যামিতি, সংখ্যা তত্ত্ব, সম্পর্কের সাধারণ তত্ত্ব এবং ক্ষেত্র এবং আয়তন নির্ধারণের পদ্ধতি, যার মধ্যে সীমা তত্ত্বের উপাদানগুলি অন্তর্ভুক্ত ছিল। গণিতের বিকাশে তার ব্যাপক প্রভাব ছিল। জ্যোতির্বিদ্যা, আলোকবিদ্যা, সঙ্গীত তত্ত্ব নিয়ে কাজ করে। ইউক্লিড (৩৬৫-৩০০ খ্রিস্টপূর্ব)

ইউক্লিডের অ্যালগরিদম ইউক্লিডের অ্যালগরিদম হল দুটি অ-নেতিবাচক পূর্ণসংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক (GCD) খুঁজে বের করার জন্য একটি অ্যালগরিদম। ইউক্লিড (৩৬৫-৩০০ খ্রিস্টপূর্বাব্দ) প্রাচীন গ্রীক গণিতবিদরা এই অ্যালগরিদমটিকে ἀνθυφαίρεσις বা ἀνταναίρεσις - "পারস্পরিক বিয়োগ" বলে অভিহিত করেছিলেন।

গণনা GCD GCD = দুটি প্রাকৃতিক সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক হল সবচেয়ে বড় সংখ্যা যার দ্বারা উভয় মূল সংখ্যা একটি অবশিষ্ট ছাড়াই বিভাজ্য। gcd(a, b)= gcd(a-b, b)= gcd(a, b-a) দুটি সংখ্যার বৃহত্তরটিকে বড় এবং ছোটের মধ্যে পার্থক্য দিয়ে প্রতিস্থাপন করুন যতক্ষণ না তারা সমান হয়। এটি NOD। gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 উদাহরণ:

স্টেপ অপারেশন M N শর্ত 1 ইনপুট M 48 2 ইনপুট N 18 3 M  N 48 18, হ্যাঁ 4 M>N 48>18, হ্যাঁ 5 M:=M-N 30 6 M  N 30  18, M> N37 >18, হ্যাঁ 8 M:=M-N 12 9 M  N 12 18, হ্যাঁ 10 M>N 12 >18, no 11 N:=N-M 6 12 M  N 12  6, হ্যাঁ 13 M>N 126 , হ্যাঁ 14 M:=M-N 6 15 M  N 6  6, no 16 আউটপুট M

প্রোগ্রাম Evklid; var m, n: পূর্ণসংখ্যা; লিখতে শুরু করুন("vved 2 chisla"); readln(m,n); mn শুরু করলে m>n হলে m:=m-n অন্য n:= n-m ; শেষ; লিখুন("nod=",m); পড়া শেষ।

0. কম্পিউটারে Evklid প্রোগ্রাম চালান। M=32, N=24 দিয়ে এটি পরীক্ষা করুন; M=696, N=234। এক . দুটি প্রদত্ত সংখ্যা কপ্রাইম কিনা তা পরীক্ষা করুন। বিঃদ্রঃ. দুটি সংখ্যাকে coprime বলা হয় যদি তাদের সর্বশ্রেষ্ঠ সাধারণ ভাজক 1 হয়। 2। LCM(n, m) = n * m / gcd(n, m) থাকলে n এবং m সংখ্যার সর্বনিম্ন সাধারণ মাল্টিপল (LCM) খুঁজুন। 3 প্রাকৃতিক সংখ্যা m এবং n দেওয়া আছে। প্রাকৃতিক সংখ্যা p এবং q খুঁজুন যার কোন সাধারণ ভাজক নেই যেমন p/q = m/n। 4. তিনটি সংখ্যার GCD নির্ণয় কর। বিঃদ্রঃ. GCD(a, b, c)= GCD(gcd(a, b), c) কার্য

পূর্বরূপ:

বিষয়: "ইউক্লিডের অ্যালগরিদম"

পাঠের উদ্দেশ্য:

1. শিক্ষাগত:

1. দুই এবং তিনটি সংখ্যার gcd বের করতে ইউক্লিড অ্যালগরিদম ব্যবহার করতে শিখুন
2. অ্যালগরিদমিক কাঠামো "শাখা" এবং "সাইকেল" ব্যবহার করার দক্ষতা একীভূত করুন
3. পাসকাল প্রোগ্রামিং ভাষায় প্রোগ্রাম লেখা এবং ডিবাগ করার অভিজ্ঞতা অর্জন করুন

1. শিক্ষাগত:

1. নতুন উপাদানের অধ্যয়নে স্বাধীনতা এবং দায়িত্ব গঠন

1. উন্নয়নশীল:

1. মনোযোগ এবং বিশ্লেষণাত্মক চিন্তার বিকাশ

পাঠ পরিকল্পনা:

1. আয়োজনের সময়
2. জ্ঞান আপডেট
3. নতুন বিষয়ের ব্যাখ্যা
4. ব্যবহারিক অংশ
5. পাঠের সারসংক্ষেপ
6. বাড়ির কাজ.

আয়োজনের সময়

শুভেচ্ছা। কে অনুপস্থিত। সংখ্যা। পাঠের বিষয়। বাড়ির কাজের উপর প্রশ্ন.

জ্ঞান আপডেট.

প্রশ্ন:

আপনি কি ধরনের অ্যালগরিদমিক কাঠামো জানেন?

রৈখিক গঠন কি? (Bl-sh)

একটি শাখা গঠন কি? (Bl-sh)

একটি চক্রীয় গঠন কি? (Bl-sh)

আপনি কি ধরনের চক্র জানেন?

কিভাবে একটি পরিচিত সংখ্যক পুনরাবৃত্তির সাথে একটি লুপ প্যাসকেল প্রোগ্রামিং ভাষায় প্রয়োগ করা হয়?

কিভাবে একটি অজানা সংখ্যক পুনরাবৃত্তির সাথে একটি লুপ প্যাসকেল প্রোগ্রামিং ভাষায় প্রয়োগ করা হয়?

একটি নতুন বিষয়ের ব্যাখ্যা (উপস্থাপনা)

ইউক্লিড সম্পর্কে;

ইউক্লিডের অ্যালগরিদমের ধারণা

এই অ্যালগরিদমের ধারণাটি ভিত্তি করে:

1. যে সম্পত্তি যদি M>N, তাহলে GCD(M, N) = GCD(M - N, N)।

অন্য কথায়, দুটি প্রাকৃতিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য (তাদের পার্থক্যের মডুলাস) এবং ছোট সংখ্যার gcd এর সমান।

প্রমাণ: K কে M এবং N (M > N) এর সাধারণ ভাজক হতে দিন। এর মানে হল M \u003d mK, N \u003d nK, যেখানে m, n হল প্রাকৃতিক সংখ্যা এবং m > n। তারপর M - N \u003d K (m - n), যা বোঝায় যে K হল M - N সংখ্যার একটি ভাজক। তাই, M এবং N সংখ্যার সকল সাধারণ ভাজক হল তাদের পার্থক্যের ভাজক M - N, সর্বশ্রেষ্ঠ সহ সাধারণ ভাজক।

2. দ্বিতীয় সুস্পষ্ট সম্পত্তি:

GCD(M, M) = M.

"ম্যানুয়াল" গণনার জন্য, ইউক্লিডের অ্যালগরিদম এইরকম দেখাচ্ছে:

1) যদি সংখ্যা সমান হয়, তাহলে তাদের যে কোনো একটিকে উত্তর হিসেবে নিন, অন্যথায় অ্যালগরিদম চালিয়ে যান;

2) সংখ্যার বৃহত্তর এবং ছোট মধ্যে পার্থক্য সঙ্গে বড় সংখ্যা প্রতিস্থাপন;

3) অনুচ্ছেদ 1 বাস্তবায়নে ফিরে যান।

ইউক্লিড অ্যালগরিদমের ব্লক ডায়াগ্রাম

জেএস প্যাসকেলে প্রোগ্রাম

প্রোগ্রাম Evklid;

var m, n: পূর্ণসংখ্যা;

শুরু

writeln("vved 2 সংখ্যা");

readln(m,n);

যখন mn করবেন

শুরু করুন

যদি m>n

তারপর m:=m-n

অন্যথায় n:=n-m;

শেষ;

লিখুন("nod=",m);

পড়া

শেষ.

ব্যবহারিক অংশ

প্রশ্ন এবং কাজ:

1. আপনার কম্পিউটারে Evklid প্রোগ্রাম চালান। এটি পরীক্ষা করুন M=32, N=24; M = 696, N = 234।
2. দুটি প্রদত্ত সংখ্যা কপ্রাইম কিনা তা পরীক্ষা করুন। বিঃদ্রঃ. দুটি সংখ্যাকে coprime বলা হয় যদি তাদের সর্বশ্রেষ্ঠ সাধারণ ভাজক 1 হয়।

পাঠের সারসংক্ষেপ

আজ পাঠে আমরা ইউক্লিড অ্যালগরিদমের সাথে পরিচিত হয়েছি, যা আমাদের দুটি অ-নেতিবাচক পূর্ণসংখ্যার GCD খুঁজে পেতে দেয়, আমরা প্যাসকেল প্রোগ্রামিং ভাষায় একটি প্রোগ্রাম লিখেছিলাম যা এই অ্যালগরিদমটি প্রয়োগ করে। বাড়িতে, আপনি একটি টাস্ক পাবেন যেখানে আপনি তিনটি সংখ্যার GCD এবং দুটি সংখ্যার LCM খুঁজে পেতে এই অ্যালগরিদমটি প্রয়োগ করবেন।

বাড়ির কাজ.

1. নিম্নলিখিত সূত্র ব্যবহার করে তিনটি সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক খুঁজে বের করার জন্য একটি প্রোগ্রাম লিখুন:

gcd(A, B, C) = gcd(gcd(A, B), C)

2. সূত্র ব্যবহার করে দুটি সংখ্যার সর্বনিম্ন সাধারণ মাল্টিপল (LCM) খুঁজে বের করার জন্য একটি প্রোগ্রাম লিখুন:

A  B \u003d GCD (A, B)  LCM (A, B)

স্লাইড 1

স্লাইড 2

স্লাইড 3

স্লাইড 4

স্লাইড 5

স্লাইড 6

স্লাইড 7

স্লাইড 2

ইউক্লিডের অ্যালগরিদম হল দুটি অ-ঋণাত্মক পূর্ণসংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক (gcd) খুঁজে বের করার জন্য একটি অ্যালগরিদম। ইউক্লিড (৩৬৫-৩০০ খ্রিস্টপূর্বাব্দ) প্রাচীন গ্রীক গণিতবিদরা এই অ্যালগরিদমটিকে ἀνθυφαίρεσις বা ἀνταναίρεσις - "পারস্পরিক বিয়োগ" বলে অভিহিত করেছিলেন।

স্লাইড 3

GCD গণনা

GCD = দুটি প্রাকৃতিক সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক হল সবচেয়ে বড় সংখ্যা যার দ্বারা উভয় মূল সংখ্যা একটি অবশিষ্ট ছাড়াই বিভাজ্য। GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) দুটি সংখ্যার বৃহত্তরটিকে বড় এবং ছোট সংখ্যার পার্থক্যের সাথে প্রতিস্থাপন করুন যতক্ষণ না তারা সমান হয়। এটি NOD। GCD (18, 45)= GCD (18, 45-18)= GCD (18, 27)= GCD (18, 9)= = GCD(9,9)=9 উদাহরণ:

স্লাইড 4

স্লাইড 5

প্রোগ্রাম Evklid; var m, n: পূর্ণসংখ্যা; লিখতে শুরু করুন ("vved 2 সংখ্যা"); readln(m,n); mn শুরু করার সময় m>n হলে m:=m-n অন্য n:=n-m; শেষ; লিখুন("nod=",m); পড়া শেষ।

স্লাইড 6

0. কম্পিউটারে Evklid প্রোগ্রাম চালান। M=32, N=24 দিয়ে এটি পরীক্ষা করুন; M=696, N=234। 1. প্রদত্ত দুটি সংখ্যা কপ্রাইম কিনা তা পরীক্ষা করুন। বিঃদ্রঃ. দুটি সংখ্যাকে coprime বলা হয় যদি তাদের সর্বশ্রেষ্ঠ সাধারণ ভাজক 1 হয়। 2. সংখ্যার সর্বনিম্ন সাধারণ মাল্টিপল (LCM) খুঁজুন এবং m যদি LCM(n, m) = n * m / gcd(n, m)। 3. প্রাকৃতিক সংখ্যা m এবং n দেওয়া আছে। সাধারণ ভাজক ছাড়া প্রাকৃতিক সংখ্যা p এবং q খুঁজুন যেমন p/q = m/n। 4. তিনটি সংখ্যার GCD নির্ণয় কর। বিঃদ্রঃ. gcd(a, b, c)= gcd(gcd(a, b), c) টাস্ক

স্লাইড 7

ইউক্লিড, প্রাচীন গ্রীক গণিতবিদ। 3য় শতাব্দীতে আলেকজান্দ্রিয়াতে কাজ করেছিলেন। বিসি e প্রধান কাজ "শুরু" (15 বই), যার মধ্যে রয়েছে প্রাচীন গণিতের ভিত্তি, প্রাথমিক জ্যামিতি, সংখ্যা তত্ত্ব, সম্পর্কের সাধারণ তত্ত্ব এবং ক্ষেত্র এবং আয়তন নির্ধারণের পদ্ধতি, যার মধ্যে সীমা তত্ত্বের উপাদানগুলি অন্তর্ভুক্ত ছিল। গণিতের বিকাশে তার ব্যাপক প্রভাব ছিল। জ্যোতির্বিদ্যা, আলোকবিদ্যা, সঙ্গীত তত্ত্ব নিয়ে কাজ করে।

সব স্লাইড দেখুন

সমস্যার বিবৃতি নিম্নলিখিত সমস্যাটি বিবেচনা করুন: দুটি প্রাকৃতিক সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক (GCD) নির্ধারণের জন্য একটি প্রোগ্রাম লিখতে হবে। গণিত মনে রাখা যাক। দুটি প্রাকৃতিক সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক হল বৃহত্তম প্রাকৃতিক সংখ্যা যার দ্বারা তারা সমানভাবে বিভাজ্য। উদাহরণস্বরূপ, 12 এবং 18 সংখ্যার সাধারণ ভাজক রয়েছে: 2, 3, 6। সর্বশ্রেষ্ঠ সাধারণ ভাজক হল সংখ্যা 6। এটি নিম্নরূপ লেখা হয়: gcd(12,18) = 6। প্রাথমিক ডেটা M এবং N হিসাবে চিহ্নিত করুন। সমস্যা বিবৃতিটি নিম্নরূপ: দেওয়া হয়েছে: M, N খুঁজুন: GCD(M, N)।

N, তারপর GCD(M,N) = GCD(M - N,N)। অন্য কথায়, দুটি প্রাকৃতিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য এবং ছোট সংখ্যার gcd এর সমান।" title="(!LANG:আলগরিদমের ধারণা এই অ্যালগরিদমের ধারণাটি সম্পত্তির উপর ভিত্তি করে যে যদি M>N হয়, তাহলে gcd(M,N) = gcd( M - N, N) অন্য কথায়, দুটি স্বাভাবিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্যের gcd এবং ছোট সংখ্যার সমান।" class="link_thumb"> 4 !}অ্যালগরিদমের ধারণা এই অ্যালগরিদমের ধারণাটি এই বৈশিষ্ট্যের উপর ভিত্তি করে যে M>N হলে GCD(M,N) = GCD(M - N,N)। অন্য কথায়, দুটি প্রাকৃতিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য এবং ছোট সংখ্যার gcd এর সমান। N, তারপর GCD(M,N) = GCD(M - N,N)। অন্য কথায়, দুটি প্রাকৃতিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য এবং ছোট সংখ্যার gcd এর সমান।> N, তারপর gcd(M,N) = gcd(M - N,N)। অন্য কথায়, দুটি প্রাকৃতিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য এবং ছোট সংখ্যার gcd এর সমান।> N, তারপর GCD(M,N) = GCD(M - N,N)। অন্য কথায়, দুটি প্রাকৃতিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য এবং ছোট সংখ্যার gcd এর সমান।" title="(!LANG:আলগরিদমের ধারণা এই অ্যালগরিদমের ধারণাটি সম্পত্তির উপর ভিত্তি করে যে M>N হলে, gcd(M,N) = gcd( M - N, N) অন্য কথায়, দুটি স্বাভাবিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য এবং ছোট সংখ্যার gcd এর সমান।"> title="অ্যালগরিদমের ধারণা এই অ্যালগরিদমের ধারণাটি এই বৈশিষ্ট্যের উপর ভিত্তি করে যে M>N হলে GCD(M,N) = GCD(M - N,N)। অন্য কথায়, দুটি প্রাকৃতিক সংখ্যার gcd তাদের ধনাত্মক পার্থক্য এবং ছোট সংখ্যার gcd এর সমান।"> !}

N)। এর মানে হল M = mK, N = pK, যেখানে m, n হল প্রাকৃতিক সংখ্যা এবং m>n। তারপর M - N = K(m - n), যেখান থেকে এটি অনুসরণ করে যে K হল M - N এর ভাজক। তাই, M এবং N-এর সকল সাধারণ ভাজক হল ভাজক" title="(!LANG:প্রুফ K কে একটি সাধারণ হতে দিন M এবং. N (M > N) এর ভাজক। এর মানে হল M = mK, N = pK, যেখানে m, n হল প্রাকৃতিক সংখ্যা, এবং m> n। তারপর M - N = K(m - n), কোথা থেকে অনুসরণ করে যে K হল M - N সংখ্যার একটি ভাজক। তাই, M এবং N সংখ্যার সকল সাধারণ ভাজক হল ভাজক" class="link_thumb"> 5 !}প্রমাণ যাক K একটি M এবং এর সাধারণ ভাজক। N (M>N)। এর মানে হল M = mK, N = pK, যেখানে m, n হল প্রাকৃতিক সংখ্যা এবং m>n। তারপর M - N = K(m - n), যেখান থেকে এটি অনুসরণ করে যে K হল M - N সংখ্যার একটি ভাজক। তাই, M এবং N সংখ্যার সকল সাধারণ ভাজক হল তাদের পার্থক্যের ভাজক M - N, সর্বশ্রেষ্ঠ সহ সাধারণ ভাজক। তাই: GCD(M,N) = GCD(M - N,N)। দ্বিতীয় সুস্পষ্ট সম্পত্তি: GCD(M,M) = M. N)। এর মানে হল M = mK, N = pK, যেখানে m, n হল প্রাকৃতিক সংখ্যা এবং m>n। তারপর M - N \u003d K (m - n), যেখান থেকে এটি অনুসরণ করে যে K হল M - N সংখ্যার একটি ভাজক। তাই, M এবং N সংখ্যার সকল সাধারণ ভাজক হল "\u003e N)। এর মানে হল M \u003d mK, N \u003d pK , যেখানে m, n হল প্রাকৃতিক সংখ্যা, এবং m > n। তারপর M - N = K(m - n), যেখান থেকে এটি অনুসরণ করে যে K হল M - N সংখ্যার একটি ভাজক। সুতরাং, M এবং N সংখ্যার সমস্ত সাধারণ ভাজক হল তাদের পার্থক্য M-N এর ভাজক, সর্বশ্রেষ্ঠ সাধারণ ভাজক সহ। অতঃপর: GCD(M, N) = GCD(M - N, N)। দ্বিতীয় সুস্পষ্ট সম্পত্তি: GCD(M , M) = M. > N)। এর মানে হল M = mK, N = pK, যেখানে m, n হল প্রাকৃতিক সংখ্যা এবং m>n। তারপর M - N = K(m - n), যেখান থেকে এটি অনুসরণ করে যে K হল M - N এর ভাজক। তাই, M এবং N-এর সকল সাধারণ ভাজক হল ভাজক" title="(!LANG:প্রুফ K কে একটি সাধারণ হতে দিন M এবং. N (M > N) এর ভাজক। এর মানে হল M = mK, N = pK, যেখানে m, n হল প্রাকৃতিক সংখ্যা, এবং m> n। তারপর M - N = K(m - n), কোথা থেকে অনুসরণ করে যে K হল M - N সংখ্যার একটি ভাজক। তাই, M এবং N সংখ্যার সকল সাধারণ ভাজক হল ভাজক"> title="প্রমাণ যাক K একটি M এবং এর সাধারণ ভাজক। N (M>N)। এর মানে হল M = mK, N = pK, যেখানে m, n হল প্রাকৃতিক সংখ্যা এবং m>n। তারপর M - N \u003d K (m - n), যা বোঝায় যে K হল M - N সংখ্যার একটি ভাজক। তাই, M এবং N সংখ্যার সকল সাধারণ ভাজক হল ভাজক"> !}

প্যাসকেল প্রোগ্রাম Evklid মধ্যে প্রোগ্রাম; var M, N: পূর্ণসংখ্যা; লিখতে শুরু করুন ("এম এবং এন লিখুন"); readln(M,N); যখন MN শুরু হয় যদি M>N তারপর M:=M-N অন্যথা N:=N-M শেষ হয়; লিখুন("HOD=",M) শেষ। N তারপর M:=M-N অন্যথা N:=N-M শেষ; লিখুন("HOD=",M) শেষ৷"> n তারপর M:=M-N else N:=N-M শেষ; লিখুন("HOD=",M) শেষ৷ শেষ; লিখুন("HOD=",M) শেষ।" title="(!LANG:Pascal program Program Evklid; var M, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N তারপর M:=M-N অন্যথা N:=N-M শেষ; লিখুন("HOD=",M) শেষ।" title="(!LANG:Pascal program Program Evklid; var M, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}