| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 376 人关注过本帖
标题:公式理解
只看楼主 加入收藏
momotianxin
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2017-6-22
结帖率:0
  已结贴   问题点数:20  回复次数:9   
公式理解
做题碰见了一个很头疼的数列
/*****************************/
小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。
并且小Q对于能否被3整除这个性质很感兴趣。
小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除
输入:包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。
输出:一个整数, 表示区间内能被3整除的数字个数。
/*****************************/
这个题看起来很简单,突然写起来的时候,发现这个数列不知道该怎么搞,弄个for循环生成保存在一个数组里面,发现到12345678910这的时候之前想出的公式又对不上了,重点是这个数列的规律怎么整呢?我必须把每个数都除3吗?
搜索更多相关主题的帖子: 公式 整除 个数 表示 数列 
2020-01-13 11:58
叶纤
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:135
专家分:141
注 册:2019-11-22
  得分:5 
你把数列输出来了l到r的除以3的个数不就出来了for循环
tem=(tem*10)+(j+1);公式然后计算符号条件的个数
2020-01-13 14:33
momotianxin
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2017-6-22
  得分:0 
回复 2楼 叶纤

不知道你的意思是不是这,如果是的话,公式不符合
int main()
{
    long long tem=0;
    int j;

    for(j=0;j<20;j++)
    {
        tem=(tem*10)+(j+1);
        printf("第%d次temp值为%lld\n",j,tem);
    }

    system("pause");
    return 0;
}   
附件: 您没有浏览附件的权限,请 登录注册
2020-01-13 15:05
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:337
帖 子:7031
专家分:41027
注 册:2011-1-18
  得分:5 
数列第i项,各位等差数列求和 s(i)=i*(i+1)/2。可见,当i为3m或3m+2时s(i)可被3整除。简单的讲,这个数列每项{否能能 否能能 否能能 ……}被3整除。
所以从数列第1项 到 第i项,共有 f(i) = i - (i+2)/3 个数可被3整数。

程序代码:
#include <stdio.h>

int main( void )
{
    unsigned l, r;
    scanf( "%u%u", &l, &r );
    printf( "%u\n", (r-(r+2)/3)-(l-1-(l+1)/3) );
}
2020-01-13 15:31
叶纤
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:135
专家分:141
注 册:2019-11-22
  得分:0 
回复 楼主 momotianxin
额😓没审清题

[此贴子已经被作者于2020-1-13 16:45编辑过]

2020-01-13 16:43
叶纤
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:135
专家分:141
注 册:2019-11-22
  得分:0 
我用unsigned long long最多19位再多就溢出


[此贴子已经被作者于2020-1-13 16:58编辑过]

附件: 您没有浏览附件的权限,请 登录注册
2020-01-13 16:55
自学的数学
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:33
帖 子:828
专家分:3590
注 册:2017-11-15
  得分:5 
从1,12,123,1234,12345,123456。。。。。。能被三整除的规律为:不能,能,能,不能,能,能。。。。。。,以三为周期循环,因而将输入的l,r分别移动至一个周期的第一个位置,在移动过程中标记需要剔除新引入的能被三整除的数目count1,标记需要加上移动过程中删除的能被三整除的数目count,再按公式(r-l)/3*2-count1+count,即可求得能被三整除的数目
程序代码:
#include<stdio.h>
int main()
{

 int l,r;

 int count = 0,count1 = 0,result = 0;

 scanf("%d%d",&l,&r);

 while(l%3 != 1)
  {
    if(l%3 == 0)
      {
         l--;
         count1++;
     }
    if(l%3 == 2)
         l--;
  }                     

 while(r%3 != 1)
  {
      if(r%3 == 0)
           {
              count++;
               r--;
           }
      if(r%3 == 2)
         {
             count++;
             r--;
         }
   }

 result = (r-l)/3*2 - count1 + count;

 printf("%d\n",result);

}
2020-01-13 19:07
momotianxin
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2017-6-22
  得分:0 
多谢各位大佬帮助,在各位,毋庸置疑4楼大神的代码,精简之至,7楼大佬的比较详细,经过我自己的总结,既然数列的规律是不能,能,能,不能,能,能...我用等效替代法,将结果表示为1,0,0,1,0,0...,也就是将1,12,123,...,123456789,12345678910...替换成1,0,0,1,0,0....然后对此数列进行操作,那么公式将被简化成 i%3 ,为1,跳过,不为1,则sum++ , 代码如下:
#include <iostream>
using namespace std;
int main()
{
    long long sum=0;
    long long l,r;
    long long temp;
    while(cin>>l>>r)
    {   
        if(l>r)
        {
            temp=l;
            l=r;
            r=l;
        }
        for(long long i=l;i<=r;i++)
        {
            if((i%3)==1)//此处将公式简化
            {
                continue;
            }
            else
            {
                sum++;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}
2020-01-14 08:41
forever74
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:CC
等 级:贵宾
威 望:25
帖 子:1280
专家分:2216
注 册:2007-12-27
  得分:5 
可能诸多程序设计教材里面老老实实从1加到100误导了初学者,
很多初学者从此以为蛮干即可。
其实不是的,能用人脑找规律的还是需要用人脑,见上。

那么为什么从1加到100提倡蛮干呢?
需要知其所以然才好。
以x86硬件为例,整数加法耗时1周期,乘法80周期,除法160周期。
所以(1+100)*100/2字面耗时241时钟周期,它不划算啊。
其实一旦你想起来除以2等于右移1位,那就变成(1+100)*100>>1那就比循环相加更快了。
所以那个蛮干程序仅仅是为了给初学者讲循环用的。
切记:只要有更好的办法,我们不蛮干。

别人能不等于你能,别人不能不等于你不能
不要问别人能不能,要说:我能
2020-01-14 10:14
momotianxin
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2017-6-22
  得分:0 
回复 9楼 forever74
恩呢,多谢
2020-01-14 13:52
快速回复:公式理解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.046205 second(s), 8 queries.
Copyright©2004-2020, BCCN.NET, All Rights Reserved