راه حل کد زشت شماره زشت


سطح دشواری ساده
ریاضی

بیان مسأله

در این مسئله به ما یک عدد داده می شود و باید بررسی کنیم که عدد زشتی است یا نه.
با توجه به اینکه اعداد زشت اعداد مثبتی هستند که عوامل اصلی آنها فقط شامل 2 ، 3 ، 5 است.
همچنین 1 معمولاً به عنوان یک عدد زشت در نظر گرفته می شود.

مثال

6
true

توضیح: 6 = 2 × 3

14
false

توضیح: 14 = 2 × 7
14 زشت نیست زیرا شامل فاکتور اصلی 7 دیگری است.

روش

از بیان مسئله مشخص است که ، برای اینکه یک عدد زشت باشد ، نباید هیچ عددی را داشته باشد عوامل اصلی غیر از 2,3،5 و XNUMX.

می دانیم که هر عدد با حاصل برخی قدرتهای یک یا چند عدد اول (به استثنای 1) حاصل می شود. از این رو می توانیم عدد را به فاکتورهای اصلی آن تقسیم کنیم و ببینیم آیا این شماره شامل اعداد اول دیگری غیر از 2,3،5 و XNUMX است یا خیر.

منظور از فاکتوراسیون اگر یک عدد اول بتواند یک عدد را کاملاً تقسیم کند ، آنگاه فاکتور آن عدد خاص خواهد بود. بنابراین اگر عدد بر 2 قابل تقسیم باشد ، می توانیم عدد داده شده را بر 2 تقسیم کنیم ، بنابراین قدرت اول عامل 1 را از بین می بریم. ما مکرراً بر 2 تقسیم می کنیم تا زمانی که تمام توان های 2 از عدد حذف شود.
به همین ترتیب ، تمام توان فاکتورهای 3 و 5 را نیز حذف خواهیم کرد.

اکنون مشخص شده است که اگر عدد شامل فاکتورهای اصلی دیگری به جز 2,3،5 و 1 باشد ، تعداد باقیمانده فعلی برابر با XNUMX نخواهد بود.
از این رو سرانجام اگر عدد 1 شود ، آن یک عدد زشت است و ما درست برمی گردیم ، وگرنه نادرست برمی گردیم.

پیاده سازی

برنامه C ++ برای راه حل کد زشت شماره زشت

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

bool isUgly(int num) 
{	
  if(num<=0) return false;
   
  while(num%2==0) num/=2;
  while(num%3==0) num/=3;
  while(num%5==0) num/=5;
  
  if(num==1) return true; 
    else return false;
}

int main() 
{
    int num=8;
  
  if(isUgly(num))
    cout<<"true"<<endl;
  else
    cout<<"false"<<endl;

  return 0; 
}
true

برنامه جاوا برای راه حل کد شماره زشت

import java.util.*;
import java.lang.*;


class UglyNumber
{  
   public static boolean isUgly(int num) 
   {
        if(num<=0) return false;
       
        while(num%2==0) num/=2;
        while(num%3==0) num/=3;
        while(num%5==0) num/=5;
        
        if(num==1) return true; 
        else return false;
        
    }
    
    public static void main(String args[])
    {
        int num=8;

        System.out.println(isUgly(num));
        
    }
}
true

تجزیه و تحلیل پیچیدگی برای راه حل کد کد زشت

پیچیدگی زمان

O (log (n)): ما عدد را به طور مکرر بر روی حلقه while در 2 ، 3 و 5 تقسیم می کنیم. از این رو پیچیدگی زمان O (log (n)) خواهد بود ، جایی که n عدد داده شده است.

پیچیدگی فضا 

O (1): ما از فضای اضافی استفاده نمی کنیم ، بنابراین ثابت است.