
平台论坛博客文库

论坛徽章:: 0

101楼 [报告]

发表于 2007-03-03 11:13 |只看该作者

恩~看完一页~有点意思~~顶一个

[ 本帖最后由 huntrsky 于 2007-3-3 11:16 编辑 ]

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cobras

小富即安

论坛徽章:: 2

102楼 [报告]

发表于 2007-03-03 13:52 |只看该作者

下面的程序是按照LZ的遍历算法编写的,但结果不正确.
前面的数只需0.几秒就出来了.但最后一个数老是出不来,另外中间少了几个数

#include <stdio.h>
unsigned f(unsigned n){
static unsigned base[][2]={
1, 0, /* 0 */
10, 0*10 +1, /* 1 */
100, 1*10 +10, /* 20 */
1000, 20*10 +100, /* 300 */
10000, 300*10 +1000, /* 4000 */
100000, 4000*10 +10000, /* 50000 */
1000000, 50000*10 +100000, /* 600000 */
10000000, 600000*10 +1000000, /* 7000000 */
100000000, 7000000*10 +10000000, /* 80000000 */
1000000000, 80000000*10+100000000, /* 900000000 */
};
int i, j;
unsigned cnt;
cnt = 0;
for(i = sizeof(base)/sizeof(base[0]) - 1; i >= 0; i--){
for(j = 0; j < 10; j++){
if(n < base[i][0]){
if(j == 1){
cnt += n + 1;
}
break;
}
cnt += base[i][1];
if(j == 1){
cnt += base[i][0];
}
n -= base[i][0];
}
}
return cnt;
}
int k(unsigned n){
static unsigned base[] = {
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000,
};
int i;
for(i = 0; i < sizeof(base)/sizeof(base[0]); i++){
if(n > base[i]){
break;
}
}
return i + 1;
}
unsigned max(unsigned a, unsigned b){
return a > b ? a : b;
}
int main(void){
static unsigned x[] = {
1,
199981,
199982,
199983,
199984,
199985,
199986,
199987,
199988,
199989,
199990,
200000,
200001,
1599981,
1599982,
1599983,
1599984,
1599985,
1599986,
1599987,
1599988,
1599989,
1599990,
2600000,
2600001,
13199998,
35000000,
35000001,
35199981,
35199982,
35199983,
35199984,
35199985,
35199986,
35199987,
35199988,
35199989,
35199990,
35200000,
35200001,
117463825,
500000000,
500000001,
500199981,
500199982,
500199983,
500199984,
500199985,
500199986,
500199987,
500199988,
500199989,
500199990,
500200000,
500200001,
501599981,
501599982,
501599983,
501599984,
501599985,
501599986,
501599987,
501599988,
501599989,
501599990,
502600000,
502600001,
513199998,
535000000,
535000001,
535199981,
535199982,
535199983,
535199984,
535199985,
535199986,
535199987,
535199988,
535199989,
535199990,
535200000,
535200001,
1111111110,
};
unsigned n;
unsigned m;
int i;
for(i = 0; i < sizeof(x)/sizeof(x[0]); i++){
m = f(x[i]);
if(m != x[i]){
printf("%u\n", x[i]);
}
}
printf("my result\n");
n = 1;
while(n < ~0){
m = f(n);
if(m == n){
printf("%u\n", m);
n++;
}else if(m > n){
n = m;
}else{
m = n + (n - m);
n = max(m / k(m), n + 1);
}
}
return 0;
}

复制代码

路小佳

稍有积蓄

论坛徽章:: 0

103楼 [报告]

发表于 2007-03-03 14:29 |只看该作者

ACM的题，怎么扯上google了?

jackk294

白手起家

论坛徽章:: 0

104楼 [报告]

发表于 2007-03-27 12:48 |只看该作者

原帖由 bleem1998 于 2006-3-29 12:14 发表
写了个伪的
大伙指正
[code]
//计算一个整数里还有多少个1，有几个返回几
int num_a_int(int papapa)
{
//这个函数对谁来说都easy吧
return 0;
}

//这个函数就是题目里要求的那个函数 ...

你这个递归太多，遇到大的数会耗尽栈内存
出现segmentatin fault

mars__1001

白手起家

论坛徽章:: 0

105楼 [报告]

发表于 2008-06-03 10:30 |只看该作者

来个快的，16毫秒，vc6

#include "math.h"
#include "stdio.h"
#include "windows.h"

#define N 19

static __int64 Sum[N+1];
static __int64 TenPow[N+1];

struct SRange
{
__int64 nBegin;
__int64 nEnd;
__int64 nLmin;
__int64 nLmax;
int n; //the numbers of the number
int nLevel;
int nIndex[N];
int nCurIndex;
int nOneAppearTimes;
};

bool CanBeDivide(SRange * pR)
{
if(pR->nBegin > pR->nLmax)
return false;

if(pR->nEnd < pR->nLmin)
return false;

return true;
}

void DivideRange(SRange * pR)
{
if(pR->nLevel == 1) //iterator end condition
{
__int64 nTotalOnes[10];
__int64 nTemp = 0;
for(int i = 0; i < 10; i++) //calculate the the numbers of the number
{
if(i == 0)
nTotalOnes[0] = pR->nLmin + pR->nOneAppearTimes;
else if(i == 1)
nTotalOnes = nTotalOnes[i-1] + pR->nOneAppearTimes + 1;
else
nTotalOnes = nTotalOnes[i-1] + pR->nOneAppearTimes;

if(nTotalOnes == pR->nBegin + i)
printf("%I64d\n", nTotalOnes);
}
return;
}
else
{
SRange range;
__int64 nLMin = pR->nLmin;
int nDivParts = pR->n == pR->nLevel ? 9 : 10;
for(int i = 0; i < nDivParts; i++)
{
range.n = pR->n;
range.nLevel = pR->nLevel - 1;

for(int j = 0; j <= pR->nCurIndex; j++)
range.nIndex[j] = pR->nIndex[j];

range.nIndex[j] = i;
range.nCurIndex = j;
range.nOneAppearTimes = pR->nOneAppearTimes;

//counter history 1 apeared times
if(range.nCurIndex == 0)
{
if(range.nIndex[range.nCurIndex] == 0)
range.nOneAppearTimes = pR->nOneAppearTimes + 1;
}
else
{
if(range.nIndex[range.nCurIndex] == 1)
range.nOneAppearTimes = pR->nOneAppearTimes + 1;
}

range.nBegin = pR->nBegin + i * TenPow[range.nLevel];
range.nEnd = pR->nBegin + (i+1) * TenPow[range.nLevel] - 1;

range.nLmin = nLMin;
range.nLmax = range.nLmin + range.nOneAppearTimes * TenPow[range.nLevel] + Sum[range.nLevel];

nLMin = range.nLmax;

if(CanBeDivide(&range))
DivideRange(&range);
}
}
}

__int64 main(__int64 argc, char* argv[])
{

unsigned int a= GetTickCount();

//iterator method
Sum[0] = 0;
Sum[1] = 1;

TenPow[0] = 1;
TenPow[1] = 10;

for(int i = 2 ; i <= N; i++)
{
TenPow = (__int64)pow(10, i);
Sum = Sum[i-1]*10 + TenPow[i-1];
}

printf("1\n");

for(i = 1; i <= N; i++)
{
SRange range;
range.nBegin = TenPow[i-1];
range.nEnd = TenPow - 1;

range.nLmin = Sum[i-1];
range.nLmax = Sum;

range.n = i;
range.nLevel = i;
range.nOneAppearTimes = 0;
range.nCurIndex = -1;

DivideRange(&range);
}
a = GetTickCount() - a;
printf("total %d ms", a);

return 0;
}

mars__1001

白手起家

论坛徽章:: 0

106楼 [报告]

发表于 2008-06-03 10:33 |只看该作者

结果：
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825
500000000
500000001
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199988
500199989
500199990
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986
501599987
501599988
501599989
501599990
502600000
502600001
513199998
535000000
535000001
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199988
535199989
535199990
535200000
535200001
1111111110
total 16 msPress any key to continue

丰衣足食

论坛徽章:: 0

107楼 [报告]

发表于 2008-08-10 21:06 |只看该作者

原帖由 michaelds 于 2007-3-2 21:57 发表
今天无意中搜到了这个帖子，Google出的题就是有味道，在尝试后发现确实考得有独到之处。纵览所有回帖，楼主对该问题是最深入，最细致，也是最接近完美答案的。
不过当把一个问题拆解到统计学的这种角度，程序本 ...

正如如果魔术的谜底被揭开了，那就没意思了。
问题不是出在魔术身上，问题出在人的大脑上。

dsdpz

白手起家

论坛徽章:: 0

108楼 [报告]

发表于 2008-08-10 22:10 |只看该作者

看了以上这些贴子，代码很多啊，大部分没细看，哈哈，也没看懂，如果要算1的话，本人的思路是这样的：个位数只有1个1，十位数1的个数为个位数与十位数的1的组合即:10.11.12.13..19，等，百位数为十位数与个位数的组合，100,111,112等，从个位数开始，一直迭加到《＝n为止。代码不写了，应该很容易实现吧，效率应该比一个个数的去循环好一点点吧