首页 > 代码库 > 凤飞飞

凤飞飞

2024-07-06 03:03:10   217人阅读

d[n]=min(dp[n-1]+1,dp[n/2]）； n为偶数
dp[n]=dp[n-1]+1; n为奇数
其实dp[n-1]和dp[n/2]哪个小呢？
我们用二进制表示一个数  因为此时n为偶数所以，尾为0，我们希望通过减去一能否可以xxxxx数出现更多的0;
1.右移动一位：减少一位，末尾的0去掉
2.减一：xxx0-1,若是xx10的形式，结果为xx01,通过减一，我们没占什么便宜,0,1总数没变。
   xxx00减去一，出现xx11，天啊，增加更多的1，算了吧，通过此处我们发现，通过减去一，我们没办法得到更多的0；
所以此题就很简单了，遇到一就减去一，遇到0就右一位，所以总次数就是count(1)X2+count(0)
count(1)就是二进制中1的个数。
#include<iostream>
using namespace std;
int main()
{

    cout<<"输入你要求的数"<<endl;
    int m;
    cin>>m;
    int sum=0;
    while(m!=1)
    {
        
        if(m&1) sum+=2;
        
        
        //得到最后一位是1，是0

          else   sum+=1;

          m=m>>1;
         

        
     
    
    
    }
    cout<<sum<<endl;
        system("pause");


return 0;
}
不用分析，直接动态规划，畅快，但效率。。。
#include<iostream>
using namespace std;
int d[2014];
int min(int x,int y)
{
    if(x>y) return y;
    else return x;

}


int main()
{
    int n;
    
    cin>>n;
    memset(d,0,sizeof(d));
    d[1]=0;
    d[2]=1;

    for(int i=3;i<=n;i++)
    {
        if(i%2==0) 
        {
            d[i]=min(d[i/2],d[i-1])+1;
        
        }
        else d[i]=d[i-1]+1;

        cout<<d[i]<<endl;
    
    
    
    }
    
    
    
    system("pause");
    

    return 0;

}

 

如果改成n为偶数则除以2，为奇数则-1或加1，那最小次数呢，如果是f(7)=4,就是说7到1至少要4次。

偶数的时候，直接右移位，不考虑。

奇数的时候，是加1还是减去1呢？

奇数可以表示为 xxxx1的形式。

 

1.减去1很简单，xxxx0的形式，

2 xxxx1呢，（a）如果xxx11加上一 就是 xxx00可能比这个还多的0,如果xxx11中11前面还有1的话，总是很爽，      (b)如果xxx01呢，加上1就是xxxx10,0的个数没变，

2中（a）是最好的，那2中（b）和 1 谁好呢？   xxxx01加上1,xxx10,xxxx01减去一，变成xxx00,显然1好。

综上所述：

.m&1==0   m=m>>1

否则 

m&10判断倒数第二位是1，是0？

为1：则 m=m+1’‘;

为0,则 m=m-1;

#include<iostream>
using namespace std;
int main()
{

    cout<<"输入你要求的数"<<endl;
    int m;
    cin>>m;
    int sum=0;
    while(m!=1)
    {
        
        if(m&1) 
        {
            sum++;
            if(m&2)
            {
                m=m+1;
            
            }
            else
            {
                m=m-1;
            
            }
        
        
        }
        
        
        //得到最后一位是1，是0

        else  
        {sum+=1;

         m=m>>1;
        }

        
         

        
     
    
    
    }
    cout<<sum<<endl;
        system("pause");


return 0;
}

 

 

 

 

 

 

 

 


联系
我们