Module: (C++) بازگشتی


Problem

5/12

بازگشت و تکرار

Theory Click to read/hide

بازگشت و تکرار
برای درک بازگشت، باید بازگشت را درک کنید...
 
تکرار در برنامه نویسی - یک مرحلهفرایند پردازش چرخه ای داده. 
اغلب الگوریتم های تکرار شونده در مرحله جاری (تکرار) از نتیجه عملیات یا عمل مشابه محاسبه شده در مراحل قبلی استفاده می کنند.  یک مثال از این محاسبات، محاسبه روابط تکراری است. 
یک مثال ساده از یک مقدار بازگشتی فاکتوریل است: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
محاسبه مقدار در هر مرحله (تکرار) \(N=N \cdot i\) است.  هنگام محاسبه مقدار \(N\)، مقدار ذخیره شده از قبل \(N\).< br />
فاکتوریل یک عدد را می توان با استفاده از فرمول بازگشتی نیز توصیف کرد:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)

ممکن است متوجه شوید که این توضیحات چیزی بیش از یک تابع بازگشتی نیست.
در اینجا خط اول (\(n <= 1\)) حالت پایه (شرط پایان بازگشت) و خط دوم انتقال به مرحله بعدی است.  < br />   <بدن>
تابع فاکتوریل بازگشتی الگوریتم تکراری
int فاکتوریل (int n) { اگر (n > 1) return n * Factorial(n - 1); else بازگشت 1; } x = 1; برای (i = 2; i <= n; i++) x = x * i; cout << x;

باید درک شود که فراخوانی تابع شامل مقداری سربار اضافی است، بنابراین یک محاسبه فاکتوریل غیر بازگشتی کمی سریعتر خواهد بود. 

نتیجه گیری:جایی که می توانید یک برنامه را با یک الگوریتم تکراری ساده و بدون بازگشت بنویسید، پس باید بدون بازگشت بنویسید. اما با این حال، دسته بزرگی از مشکلات وجود دارد که در آن فرآیند محاسباتی تنها با استفاده از بازگشت اجرا می شود.
از سوی دیگر، الگوریتم های بازگشتی اغلب قابل درک تر هستند.
 

Problem

تابعی را تعریف کنید K(n) که تعداد ارقام یک عدد طبیعی معین را برمی گرداند n به صورت

\(\begin{equation*} K(n) = \begin{cases} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{if n >= 10} \end{cases} \end{equation*}\).

یک تابع بازگشتی بنویسید تا تعداد ارقام یک عدد طبیعی n را با استفاده از نسبت بالا محاسبه کنید.

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include<iostream>
using namespace std;

int CountDigit(int n)
{            
  return 1 + CountDigit(n / 10);
}

main()
{
  int n;
  cin >> n;
  cout << CountDigit(n);
}

     

Program check result

To check the solution of the problem, you need to register or log in!