এখানে আমরা দেখব কিভাবে Stern’s Diatomic সিরিজে nth শব্দটি বের করা যায়। সিরিজটি হল 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, … এটি fusc ফাংশন নামেও পরিচিত। এই সিরিজটিকে −
হিসাবে সংজ্ঞায়িত করা যেতে পারে𝑝(𝑛)=$p\lgroup\frac{n}{2}\rgroup$ 𝑤ℎ𝑒𝑛 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
𝑝(𝑛)=$p\lgroup\frac{n-1}{2}\rgroup+p\lgroup\frac{n+1}{2}\rgroup$ 𝑤ℎ𝑒𝑛 𝑛 𝑖𝑠 𝑜𝑑𝑠 𝑜𝑑𝑠
𝑝(0)=0 𝑎𝑛𝑑 𝑝(1)=1
এখানে আমরা গণনার সংখ্যা কমাতে ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব। p(0) এবং p(1) এর জন্য বেস কেস সংরক্ষণ করার পরে, আমরা সূচক i =2 থেকে n এ পুনরাবৃত্তি করব এবং p(i) গণনা করব
উদাহরণ
#include<iostream> using namespace std; int findTerm(int n) { int table[n+1]; table[0] = 0; table[1] = 1; for (int i = 2; i <= n; i++) { if (i % 2 == 0) table[i] = table[i / 2]; else table[i] = table[(i - 1) / 2] + table[(i + 1) / 2]; } return table[n]; } int main() { cout << 3 << " rd term is: " << findTerm(3) << endl; cout << 15 << " th term is: " << findTerm(15) << endl; cout << 20 << " th term is: " << findTerm(20) << endl; }
আউটপুট
3 rd term is: 2 15 th term is: 4 20 th term is: 3