در این مطلب، روش نوشتن برنامه شمارش اعداد فاقد ۳ مورد بررسی قرار گرفته است. عدد n داده شده است. هدف نوشتن تابعی است که تعداد اعداد از ۱ تا n که در ارقام خود ۳ ندارند (در ارائه اعشاری) را در خروجی بازگرداند.

مثال:

Input: n = 10
Output: 9

Input: n = 45
Output: 31
// Numbers 3, 13, 23, 30, 31, 32, 33, 34,
// ۳۵, ۳۶, ۳۷, ۳۸, ۳۹, ۴۳ contain digit 3.

Input: n = 578
Output: 385

روش شمارش اعداد فاقد ۳

این مساله را می‌توان به صورت بازگشتی حل کرد. فرض می‌شود که تابع (count(n، تعداد اعداد فاقد رقم ۳ را می‌شمارد.

‘msd’ –> the most significant digit in n
‘d’ –> number of digits in n.

count(n) = n if n < 3

count(n) = n – 1 if 3 <= n 10 and msd is not 3

count(n) = count( msd * (10^(d-1)) – 1)
if n > 10 and msd is 3

در ادامه، راهکار استفاده شده در بالا، برای مثال، روی عدد n = 578 پیاده‌سازی می‌شود.

count(578) = 4*count(99) + 4 + count(78)

عبارت میانی ۴، برای شامل شدن ارقام ۱۰۰، ۲۰۰، ۴۰۰ و ۵۰۰ اضافه شده است. اکنون، n = ۳۵ به عنوان مثال دیگری، مورد بررسی  قرار گرفته است.

count(35) = count (3*10 – 1) = count(29)

برنامه شمارش اعداد فاقد ۳ در ++C

#include <bits/stdc++.h> 
using namespace std; 

/* returns count of numbers which are 
in range from 1 to n and don't contain 3 
as a digit */
int count(int n) 
{ 
// Base cases (Assuming n is not negative) 
if (n < 3) 
return n; 
if (n >= 3 && n < 10) 
return n-1; 

// Calculate 10^(d-1) (10 raise to the power d-1) where d is 
// number of digits in n. po will be 100 for n = 578 
int po = 1; 
while (n/po > 9) 
po = po*10; 

// find the most significant digit (msd is 5 for 578) 
int msd = n/po; 

if (msd != 3) 
// For 578, total will be 4*count(10^2 - 1) + 4 + count(78) 
return count(msd)*count(po - 1) + count(msd) + count(n%po); 
else
// For 35, total will be equal to count(29) 
return count(msd*po - 1); 
} 

// Driver code 
int main() 
{ 
cout << count(578) << " "; 
return 0; 
} 

// This code is contributed by rathbhupendra

برنامه شمارش اعداد فاقد ۳ در C

#include <stdio.h> 

/* returns count of numbers which are in range from 1 to n and don't contain 3 
as a digit */
int count(int n) 
{ 
// Base cases (Assuming n is not negative) 
if (n < 3) 
return n; 
if (n >= 3 && n < 10) 
return n-1; 

// Calculate 10^(d-1) (10 raise to the power d-1) where d is 
// number of digits in n. po will be 100 for n = 578 
int po = 1; 
while (n/po > 9) 
po = po*10; 

// find the most significant digit (msd is 5 for 578) 
int msd = n/po; 

if (msd != 3) 
// For 578, total will be 4*count(10^2 - 1) + 4 + count(78) 
return count(msd)*count(po - 1) + count(msd) + count(n%po); 
else
// For 35, total will be equal to count(29) 
return count(msd*po - 1); 
} 

// Driver program to test above function 
int main() 
{ 
printf ("%d ", count(578)); 
return 0; 
}

برنامه شمارش اعداد فاقد ۳ در جاوا

// Java program to count numbers that not contain 3 
import java.io.*; 

class GFG 
{ 
// Function that returns count of numbers which 
// are in range from 1 to n 
// and not contain 3 as a digit 
static int count(int n) 
{ 
// Base cases (Assuming n is not negative) 
if (n < 3) 
return n; 
if (n >= 3 && n < 10) 
return n-1; 

// Calculate 10^(d-1) (10 raise to the power d-1) where d is 
// number of digits in n. po will be 100 for n = 578 
int po = 1; 
while (n/po > 9) 
po = po*10; 

// find the most significant digit (msd is 5 for 578) 
int msd = n/po; 

if (msd != 3) 
// For 578, total will be 4*count(10^2 - 1) + 4 + count(78) 
return count(msd)*count(po - 1) + count(msd) + count(n%po); 
else
// For 35, total will be equal to count(29) 
return count(msd*po - 1); 
} 

// Driver program 
public static void main (String[] args) 
{ 
int n = 578; 
System.out.println(count(n)); 
} 
} 

// Contributed by Pramod Kumar

برنامه شمارش اعداد فاقد ۳ در پایتون

# Python program to count numbers upto n that don't contain 3 

# Returns count of numbers which are in range from 1 to n 
# and don't contain 3 as a digit 
def count(n): 

# Base Cases ( n is not negative) 
if n < 3: 
return n 
elif n >= 3 and n < 10: 
return n-1

# Calculate 10^(d-1) ( 10 raise to the power d-1 ) where d 
# is number of digits in n. po will be 100 for n = 578 

po = 1
while n/po > 9: 
po = po * 10

# Find the MSD ( msd is 5 for 578 ) 
msd = n/po 

if msd != 3: 
# For 578, total will be 4*count(10^2 - 1) + 4 + ccount(78) 
return count(msd) * count(po-1) + count(msd) + count(n%po) 
else: 
# For 35 total will be equal to count(29) 
return count(msd * po - 1) 

# Driver Program 
n = 578
print count(n) 

# Contributed by Harshit Agrawal

برنامه شمارش اعداد فاقد ۳ در #C

// C# program to count numbers that not 
// contain 3 
using System; 

class GFG { 

// Function that returns count of 
// numbers which are in range from 
// ۱ to n and not contain 3 as a 
// digit 
static int count(int n) 
{ 

// Base cases (Assuming n is 
// not negative) 
if (n < 3) 
return n; 
if (n >= 3 && n < 10) 
return n-1; 

// Calculate 10^(d-1) (10 raise 
// to the power d-1) where d is 
// number of digits in n. po will 
// be 100 for n = 578 
int po = 1; 

while (n / po > 9) 
po = po * 10; 

// find the most significant 
// digit (msd is 5 for 578) 
int msd = n / po; 

if (msd != 3) 

// For 578, total will be 
// ۴*count(10^2 - 1) + 4 + 
// count(78) 
return count(msd) * count(po - 1) 
+ count(msd) + count(n % po); 
else

// For 35, total will be equal 
// to count(29) 
return count(msd * po - 1); 
} 

// Driver program 
public static void Main () 
{ 
int n = 578; 

Console.Write(count(n)); 
} 
} 

// This code is contributed by Sam007.

برنامه شمارش اعداد فاقد ۳ در PHP

<?php 
/* returns count of numbers which are in range 
from 1 to n and don't contain 3 as a digit */
function count1($n) 
{ 

// Base cases (Assuming n is not negative) 
if ($n < 3) 
return $n; 
if ($n >= 3 && $n < 10) 
return $n-1; 

// Calculate 10^(d-1) (10 raise to the 
// power d-1) where d is number of digits 
// in n. po will be 100 for n = 578 
$po = 1; 
for($x = intval($n/$po); $x > 9; $x = intval($n/$po)) 
$po = $po*10; 

// find the most significant digit (msd is 5 for 578) 
$msd = intval($n / $po); 

if ($msd != 3) 

// For 578, total will be 4*count(10^2 - 1) 
// + ۴ + count(78) 
return count1($msd) * count1($po - 1) + 
count1($msd) + count1($n%$po); 
else

// For 35, total will be equal to count(29) 
return count1($msd*$po - 1); 
} 

// Driver program to test above function 
echo count1(578); 

// This code is contributed by mits. 
?>

خروجی

۳۸۵

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

 

منبع [+]