一路笔试题，没有想到好方法，求解

一道笔试题，没有想到好方法，求解
已知
1/1=1
1/2=0.5
1/3=0.(3)
1/4=0.25
1/5=0.2
1/6=0.1(6)
1/7=0.(142857)
1/8=0.125
1/9=0.(1)
上面大括号的意思是无线循环的数字，例如0.(3)就是循环3这一个数字，0.(142857)就循环了6个数字，
求1到1000中循环数字最多的是哪个数，并且求出循环的数字。

求助！思路  我确实没想到好方法。求 大家 帮忙一下

[解决办法]

import java.util.ArrayList;


public class Main{
public static void main(String[] args){
int n = -1;
int[] ret = new int[0];

for(int i=1; i<=1000; ++i){
int[] t = divide(i);

if(t.length > ret.length){
n = i;
ret = t;
}
}

System.out.println(n);

for(int i=0; i<ret.length; ++i){
System.out.print(ret[i]+" ");
}
}

private static int[] divide(int n){
ArrayList<Integer> cycle = new ArrayList<Integer>();
ArrayList<Integer> list = new ArrayList<Integer>();
int p = 1;
int r = -1;

while(true){
while(p < n){
p *= 10;
}

r = p%n;

if(r==0 
[解决办法]
 list.indexOf(r)!=-1){
break;
}

list.add(r);
cycle.add(p/n);
p = r;
}

if(r == 0){
return new int[0];
}

int start = list.indexOf(r);

int[] ret = new int[cycle.size()-start];
for(int i=0; i<ret.length; ++i){
ret[i] = cycle.get(i+start);
}

return ret;
}
}

这个数是983，循环节长度是884
[解决办法]
估计楼主在困扰如何判断是不是无限循环小数

[解决办法]

int GetRepetendNum(int n)
{
    int sum=0;
    for(int i=1;;i++)
    {
        sum=sum*10+9;
        sum%=n;
        if(sum==0)
            return i;
    }
    return 0;
}

[解决办法]
楼上的代码俺没看，不过俺觉得，这个问题应该不难，可以模拟手算除法，并将余数写入集合，当当前余数已存在集合中的时候，循环结束，循环数字的个数则由此可以统计出来，最后取其最大输出即可。
[解决办法]
1楼结果不对，求的是循环的长度，不是小数位数，并且少算了0，

#include <stdio.h>
#include <vector>
int calc_clr(int n)
{
int div =1;
std::vector<int> vect;
while(div<n)
{
div*=10;
}
if (0==div%n)
return 0;
while (1)
{
int remain = div%n;
if (0==remain)
return 0;
for (int i = 0;i < vect.size();i++)
{
if (vect_bit[i]==remain)
return vect_bit.size()-i;
}
vect_bit.push_back(remain);
div =remain*10;

while(div<n)
{
div*=10;
vect_bit.push_back(div);
}

}
return 0;



}

int main ()
{
int max_num =0;
int max_i =0;
for (int i =1 ;i<1000;i++)
{
int clr_num = calc_clr(i);
printf("i=%d,clr_num=%d \n",i,clr_num);
if (clr_num >max_num)
{
max_num =clr_num;
max_i =i;

}

//if (i%50==0)
//getchar();
}
printf("max_i=%d,max_num=%d \n",max_i,max_num);
getchar();
}

[解决办法]
循环的部分还比较难判断, 不知道有可能除了这样的结果.

0.23234562323456789...

这样的话, 什么时候才是个头呀, 不好判断什么时候该结束这个除法.


[解决办法]

#include <iostream>
#include <map>
using namespace std;

void divide(int n, map<int, int> *cycle){
int p = 1;
int r = -1;
for(;;){
while(p < n) p *= 10;
r = p % n;
if(r == 0 
[解决办法]
 (*cycle).find(r) != (*cycle).end()) break;
(*cycle).insert(pair<int, int> (r, p / n));
p = r;
}
}


int main() {
int n = -1; 
 
map<int, int> p;//保存余数,除数
map<int, int> tmp;
for(int i = 1; i <= 1000; i++){
divide(i, &tmp);
if(p.size() < tmp.size()){
            p = tmp;
            n = i;
}
tmp.clear();
}
cout << n << endl;
map<int, int>::iterator it;
for(it = p.begin(); it != p.end(); it++){
cout << it->second << " ";
}
cout << endl;
cout << p.size() << endl;

return 0;
}

[解决办法]
对于一个奇数k ，如果k 不是5的倍数
如果9。。。9/k 无余数，  则9的个数就是小数 1/k 的循环节长度。
[解决办法]

[解决办法]

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <map>

#define SHOW_ALL//为测试，显示所有数字的循环节

#ifdef SHOW_ALL
#define SHOW_FILE//输出在文件中
#endif

//返回1/num的循环节有多少个数字
int getbit(int num
#ifdef SHOW_ALL
   , std::vector<int>& vec
#endif //SHOW_ALL
   )
{
std::map<int, int> bits;//某一余数出现的商的位置记录
std::vector<int> vectemp;
int x = 1;//现在的余数
int count = 0;//现在商的位置

while (true)
{
#ifdef SHOW_ALL
vectemp.push_back(x / num);
#endif //SHOW_ALL

x %= num;

if (x == 0)//有限小数
return 0;

std::map<int, int>::iterator it = bits.find(x);
if (it == bits.end())
{
bits.insert(std::make_pair(x, count));
}
else//找到循环节
{
#ifdef SHOW_ALL
vec.insert(vec.end(), vectemp.begin() + it->second + 1, vectemp.begin() + count + 1);
#endif //SHOW_ALL
return count - it->second;
}

x *= 10;//末尾添0
++count;

while (x < num)//末尾添0
{
bits.insert(std::make_pair(x, count));
x *= 10;
++count;
#ifdef SHOW_ALL
vectemp.push_back(0);
#endif //SHOW_ALL
}
}
}

int function()
{
int max = 0;//循环节最大位数
int r = 0;//所在的数字
#ifdef SHOW_FILE
std::wfstream f(L"file.txt", std::fstream::trunc 
[解决办法]
 std::fstream::out);
#endif //SHOW_ALL
for (int i = 1; i <= 1000; ++i)
{
#ifdef SHOW_ALL
std::vector<int> vec;
int v = getbit(i, vec);
#ifdef SHOW_FILE
f
#else //SHOW_FILE
std::wcout 
#endif //SHOW_FILE
<< i << L"[" << vec.size() << L"]:";
for (std::vector<int>::const_iterator it = vec.begin(), et = vec.end(); it != et; ++it)
{
#ifdef SHOW_FILE
f
#else //SHOW_FILE
std::wcout
#endif //SHOW_FILE
<< *it;
}
#ifdef SHOW_FILE
f
#else //SHOW_FILE
std::wcout
#endif //SHOW_FILE
<< std::endl;
#else //SHOW_ALL
int v = getbit(i);
#endif //SHOW_ALL
if (max < v)
{
max = v;
r = i;
}
}
#ifdef SHOW_FILE
f.close();
#endif
return r;
}

int _tmain(int argc, _TCHAR* argv[])
{
int num = function();

std::wcout << L"Result:" << num << std::endl;

system("pause");

return 0;
}

查看更多 下一篇